跟我一起阅读Java源代码之HashMap

Posted on

跟我一起阅读Java源代码之HashMap

最近闲的很，想和大家一起学习并讨论下Java的一些源代码以及其实现的数据结构，

不是什么高水平的东西，有兴趣的随便看看

  1. 为什么要用Map，以HashMap为例

    很多时候我们有这样的需求，我们需要将数据成键值对的方式存储起来，根据key来获取value(value可以是简单值，也可以是自定义对象)

    当然用对象数组也能实现这个目的，查找时可以遍历数组，比较关键字来获取对应的value

    从性能上来讲，遍历大数组会消耗性能

    从API易用性来讲，需要自己实现查找的逻辑

    所以用HashMap是必要的

  1. HashMap的数据结构是怎么样的
我一直对HashMap的内部结构很好奇，看了源码之后发现他是用散列实现的，即基于hashcode

大体思想是这样的

1. 首先建立一个数组用来存取数据，假设我们定义一个Object[] table用来存取map的value

这个很容易理解，key存在哪里呢？暂时我不想存储key

2. 获得key的hashcode经过一定算法转成一个整数

    index，这个index的取值范围必须是0=<index<table.length，然后我将其作为数组元素的下标

    比如执行这样的操作：table[index] = value;

    这样存储的问题解决了

3. 如何通过key去获取这个value呢

    这个太简单了，首先获取key的hashcode，然后通过刚才一样的算法得出元素下标index

    然后value = table[index]

简单的HashTable实现如下

Java代码 收藏代码

  1. public class SimpleHashMap {
  3. private Object[] table;
  5. public SimpleHashMap() {
  6. table = new Object[10];
  7. }
  9. public Object get(Object key) {
  10. int index = indexFor(hash(key.hashCode()), 10);
  11. return table[index];
  12. }
  14. public void put(Object key, Object value) {
  15. int index = indexFor(hash(key.hashCode()), 10);
  16. table[index] = value;
  17. }
  19. ///
  20. /* 通过hash code 和table的length得到对应的数组下标
  21. /*
  22. /* @param h
  23. /* @param length
  24. /* @return
  25. /*/
  26. static int indexFor(int h, int length) {
  27. return h & (length - 1);
  28. }
  30. ///
  31. /* 通过一定算法计算出新的hash值
  32. /*
  33. /* @param h
  34. /* @return
  35. /*/
  36. static int hash(int h) {
  37. h ^= (h >>> 20) ^ (h >>> 12);
  38. return h ^ (h >>> 7) ^ (h >>> 4);
  39. }
  42. public static void main(String[] args){
  43. SimpleHashMap hashMap = new SimpleHashMap();
  44. hashMap.put("key", "value");
  45. System.out.println(hashMap.get("key"));
  46. }
  47. }

这个简单的例子大概描述了散列实现hashmap的过程

但是还很不成熟，我发现至少存在以下两个问题

  1. hashmap的size是固定的

  2. 如果不同的key通过hashcode得出的index相同呢，这样的情况是存在的，如何解决？ 来源： [http://tangyanbo.iteye.com/blog/1755636](http://tangyanbo.iteye.com/blog/1755636) 由于table的大小是有限的，而key的集合范围是无限大的，所以寄希望于hashcode散落，肯定会出现多个key散落在同一个数组下标下面，

因此我们要引入另外一个概念，将key和value同时存入table[index]中，即将key和value构成一个对象放在table[index]，而且可能存放多个，他们的key对应的index相同，但是key本身不同

现在我们就该讨论以什么样的方式存储这些散落在同一个数组下标的元素

可以考虑数组？

也可以考虑链表存储

源码里面是用链表存储的，其实我也没明白这两种方式在这里有什么区别

，感觉无论在检索和存储上都是差不多的效率，

检索都是需要遍历的方式，而存储也可以是顺序的

那这个问题留给大家吧。

我们来实现链式存储的方式，首先定义一个链表数据结构Entry：

Java代码 收藏代码

  1. public class Entry {
  2. //存储key
  3. final K key;
  4. //存储value
  5. V value;
  6. //存储指向下一个节点的指针
  7. Entry next;
  8. //存储key映射的hash
  9. final int hash;
  10. }

新的EntryHashMap实现方式

Java代码 收藏代码

  1. public class EntryHashMap {
  3. transient Entry[] table;
  5. transient int size;
  7. public V put(K key, V value) {
  8. //计算出新的hash
  9. int hash = hash(key.hashCode());
  10. //计算出数组小标i
  11. int i = indexFor(hash, table.length);
  12. //遍历table[i]，如果table[i]没有与新加入的key相等的，则新加入
  13. //一个value到table[i]中的entry，否则将新的value覆盖旧的value并返回旧的value
  14. for (Entry e = table[i]; e != null; e = e.next) {
  15. Object k;
  16. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  17. V oldValue = e.value;
  18. e.value = value;
  19. return oldValue;
  20. }
  21. }
  22. addEntry(hash, key, value, i);
  23. return null;
  24. }
  26. public void addEntry(int hash, K key, V value, int bucketIndex) {
  27. Entry e = table[bucketIndex];
  28. //将新的元素插入链表前端
  29. table[bucketIndex] = new Entry<>(hash, key, value, e);
  30. size++;
  31. }
  33. ///
  34. /* 通过hash code 和table的length得到对应的数组下标
  35. /*
  36. /* @param h
  37. /* @param length
  38. /* @return
  39. /*/
  40. static int indexFor(int h, int length) {
  41. return h & (length - 1);
  42. }
  44. ///
  45. /* 通过一定算法计算出新的hash值
  46. /*
  47. /* @param h
  48. /* @return
  49. /*/
  50. static int hash(int h) {
  51. h ^= (h >>> 20) ^ (h >>> 12);
  52. return h ^ (h >>> 7) ^ (h >>> 4);
  53. }
  54. }

来源： [http://tangyanbo.iteye.com/blog/1756074](http://tangyanbo.iteye.com/blog/1756074) 为什么要用链表而不是数组

链表的作用有如下两点好处

  1. remove操作时效率高，只维护指针的变化即可，无需进行移位操作

  2. 重新散列时，原来散落在同一个槽中的元素可能会被散落在不同的地方，对于数组需要进行移位操作，而链表只需维护指针

今天研究下数组长度不够时的处理办法

table为散列数组

  1. 首先定义一个不可修改的静态变量存储table的初始大小 DEFAULT_INITIAL_CAPACITY

  2. 定义一个全局变量存储table的实际元素长度，size

  3. 定义一个全局变量存储临界点，即元素的size>=threshold这个临界点时，扩大table的容量

  4. 因为index是根据hash和table的长度计算得到的，所以还需要重新对所有元素进行散列

实现如下：

Java代码 收藏代码

  1. package sourcecoderead.collection.map;
  4. public class EntryHashMap {
  6. /// 初始容量 /*/
  7. static final int DEFAULT_INITIAL_CAPACITY = 16;
  9. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  11. /// 下次扩容的临界值 /*/
  12. int threshold;
  14. transient int size;
  16. final float loadFactor;
  18. transient Entry[] table;
  20. public EntryHashMap() {
  21. this.loadFactor = DEFAULT_LOAD_FACTOR;
  22. threshold = (int) (DEFAULT_INITIAL_CAPACITY /* DEFAULT_LOAD_FACTOR);
  23. table = new Entry[DEFAULT_INITIAL_CAPACITY];
  24. }
  26. public V put(K key, V value) {
  27. // 计算出新的hash
  28. int hash = hash(key.hashCode());
  29. // 计算出数组小标i
  30. int i = indexFor(hash, table.length);
  31. // 遍历table[i]，如果table[i]没有与新加入的key相等的，则新加入
  32. // 一个value到table[i]中的entry，否则将新的value覆盖旧的value并返回旧的value
  33. for (Entry e = table[i]; e != null; e = e.next) {
  34. Object k;
  35. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  36. V oldValue = e.value;
  37. e.value = value;
  38. return oldValue;
  39. }
  40. }
  41. addEntry(hash, key, value, i);
  42. return null;
  43. }
  45. public V get(K key) {
  46. // 计算出新的hash
  47. int hash = hash(key.hashCode());
  48. // 计算出数组小标i
  49. int i = indexFor(hash, table.length);
  50. for (Entry e = table[i]; e != null; e = e.next) {
  51. Object k;
  52. if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  53. return e.value;
  54. }
  55. }
  56. return null;
  57. }
  59. private void addEntry(int hash, K key, V value, int bucketIndex) {
  60. Entry e = table[bucketIndex];
  61. // 将新的元素插入链表前端
  62. table[bucketIndex] = new Entry<>(hash, key, value, e);
  63. if (size++ >= threshold)
  64. resize(2 /* table.length);
  65. }
  67. void resize(int newCapacity) {
  68. Entry[] oldTable = table;
  69. int oldCapacity = oldTable.length;
  70. Entry[] newTable = new Entry[newCapacity];
  71. transfer(newTable);
  72. table = newTable;
  73. threshold = (int) (newCapacity /* loadFactor);
  74. }
  76. void transfer(Entry[] newTable) {
  77. Entry[] src = table;
  78. int newCapacity = newTable.length;
  79. for (int j = 0; j < src.length; j++) {
  80. Entry e = src[j];
  81. if (e != null) {
  82. src[j] = null;
  83. do {
  84. Entry next = e.next;
  85. int i = indexFor(e.hash, newCapacity);
  86. e.next = newTable[i];
  87. newTable[i] = e;
  88. e = next;
  89. } while (e != null);
  90. }
  91. }
  92. }
  94. ///
  95. /* 通过hash code 和table的length得到对应的数组下标
  96. /*
  97. /* @param h
  98. /* @param length
  99. /* @return
  100. /*/
  101. static int indexFor(int h, int length) {
  102. return h & (length - 1);
  103. }
  105. ///
  106. /* 通过一定算法计算出新的hash值
  107. /*
  108. /* @param h
  109. /* @return
  110. /*/
  111. static int hash(int h) {
  112. h ^= (h >>> 20) ^ (h >>> 12);
  113. return h ^ (h >>> 7) ^ (h >>> 4);
  114. }
  116. public static void main(String[] args) {
  117. EntryHashMap hashMap = new EntryHashMap();
  118. hashMap.put("key", "value");
  119. System.out.println(hashMap.get("key"));
  120. }
  121. }

来源： [http://tangyanbo.iteye.com/blog/1756536](http://tangyanbo.iteye.com/blog/1756536)

希望本站内容对您有点用处,有什么疑问或建议请在后面留言评论
转载请注明作者(RobinChia)和出处 It so life ，请勿用于任何商业用途
本文链接: 跟我一起阅读Java源代码之HashMap