三位数组实现的HashMap

红太狼 2022-02-02 14:45 116阅读 0赞

网上的一个HashMap代码，用三个数组实现，不同于jdk中的实现方式。处理哈希冲突是采用二次哈希（再哈希）的策略，学习了一把，个别地方可能没有理解到位。写了一些注释，如果有错误，敬请指出。

Java代码 ![收藏代码][icon_star.png]

1.  **public****final****class** LongHashMap \{ 
2.  
3.  
4.  **protected****long** table\[\];//存放键,类型为long,应该是用于特殊场所
5.  **protected** Object values\[\];//存放值
6.  **protected****byte** state\[\];//state\[i\]=0,1,2表示table\[i\]与values\[i\]没有使用,已经使用,已删除
7.  **protected****int** freeEntries;//空闲的空间数
8.  
9.  **protected****int** distinct;//当前存了多少对键值
10. 
11. **protected****int** lowWaterMark;//当LongHashMap存放的键值对少于此数时,将重新调整(再哈希）
12. **protected****int** highWaterMark;//当LongHashMap存放的键值对大于此数时,将重新调整,由容量和装载因子决定
13. 
14. 
15. **protected****double** minLoadFactor;//最小装载因子
16. **protected****double** maxLoadFactor;//最大装载因子
17. 
18. // 如果元素放得太满，就必须进行rehash(再哈希)。再哈希使空间增大，并将原有的对象重新导入新的LongHashMap中，
19. //而原始的LongHashMap被删除。loadfactor(装载因子)决定何时要对LongHashMap进行再哈希。
20. **protected****static****final****int** DEFAULT\_CAPACITY = 277;//缺省的容量,一个素数
21. **protected****static****final****double** DEFAULT\_MIN\_LOAD\_FACTOR = 0.2;//缺省的最小的装载因子
22. **protected****static****final****double** DEFAULT\_MAX\_LOAD\_FACTOR = 0.6;//缺省的最大的装载因子
23. 
24. **protected****static****final****byte** FREE = 0; 
25. **protected****static****final****byte** FULL = 1; 
26. **protected****static****final****byte** REMOVED = 2; 
27. 
28. //用缺省的容量构建HashMap
29. **public** LongHashMap() \{ 
30. **this**(DEFAULT\_CAPACITY); 
31.  \} 
32. 
33. //构造函数
34. **public** LongHashMap(**int** initialCapacity) \{ 
35. **this**(initialCapacity, DEFAULT\_MIN\_LOAD\_FACTOR, DEFAULT\_MAX\_LOAD\_FACTOR); 
36.  \} 
37. 
38. //构造函数
39. **public** LongHashMap(**int** initialCapacity, **double** minLoadFactor, **double** maxLoadFactor) \{ 
40.  setUp(initialCapacity,minLoadFactor,maxLoadFactor); 
41.  \} 
42. 
43. //使用指定的初始化容量,最小装载因子,最大装载因子构建LongHashMap
44. **protected****void** setUp(**int** initialCapacity, **double** minLoadFactor, **double** maxLoadFactor) \{ 
45. **if** (initialCapacity < 0) \{ //参数检查
46. **throw****new** IllegalArgumentException( 
47. "Initial Capacity must not be less than zero: "\+ initialCapacity 
48.  ); 
49.  \} 
50. **if** (minLoadFactor < 0.0 || minLoadFactor >= 1.0) \{ 
51. **throw****new** IllegalArgumentException( 
52. "Illegal minLoadFactor: "\+ minLoadFactor 
53.  ); 
54.  \} 
55. **if** (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) \{ 
56. **throw****new** IllegalArgumentException( 
57. "Illegal maxLoadFactor: "\+ maxLoadFactor 
58.  ); 
59.  \} 
60. **if** (minLoadFactor >= maxLoadFactor) \{ 
61. **throw****new** IllegalArgumentException( 
62. "Illegal minLoadFactor: " \+ minLoadFactor +

本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/archive/2012/12/26/2834234.html，如需转载请自行联系原作者

[icon_star.png]: /images/20220202/c70856a174924afcbf179f6c53148007.png