[关闭]
@kiraSally 2018-03-12T18:32:49.000000Z 字数 11968 阅读 4733

集合番@HashMap一文通(1.7版)

JAVA COLLECTIONS 源码 1.7版本


1.HashMap的定义

2.HashMap的数据结构

2.1 类定义

  1. public class HashMap<K,V>
  2. extends AbstractMap<K,V>
  3. implements Map<K,V>, Cloneable, Serializable

2.2 重要全局变量

链表散列的数据结构(数组+链表【冲突解决方案-封闭寻址方法】)

  1. 备注:建议直接看英文注释,更加清晰明了
  2. //The default initial capacity - MUST be a power of two.
  3. static final int DEFAULT_INITIAL_CAPACITY = 16;
  4. //The maximum capacity - MUST be a power of two <= 1<<30.
  5. static final int MAXIMUM_CAPACITY = 1 << 30;
  6. //The load factor used when none specified in constructor.
  7. static final float DEFAULT_LOAD_FACTOR = 0.75f;
  8. //The table, resized as necessary. Length MUST Always be a power of two.
  9. transient Entry<K,V>[] table;
  10. //The number of key-value mappings contained in this map.
  11. transient int size;
  12. //The next size value at which to resize (capacity * load factor).
  13. int threshold;
  14. //The load factor for the hash table.
  15. final float loadFactor;
  16. /**
  17. * The number of times this HashMap has been structurally modified
  18. * Structural modifications are those that change the number of mappings in
  19. * the HashMap or otherwise modify its internal structure (e.g.,
  20. * rehash). This field is used to make iterators on Collection-views of
  21. * the HashMap fail-fast. (See ConcurrentModificationException).
  22. */
  23. transient int modCount;

2.3 构造器

  1. public HashMap(int initialCapacity, float loadFactor) {
  2. if (initialCapacity < 0)
  3. throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
  4. if (initialCapacity > MAXIMUM_CAPACITY)
  5. initialCapacity = MAXIMUM_CAPACITY;
  6. if (loadFactor <= 0 || Float.isNaN(loadFactor))
  7. throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
  8. // Find a power of 2 >= initialCapacity
  9. int capacity = 1;
  10. while (capacity < initialCapacity)
  11. capacity <<= 1;
  12. this.loadFactor = loadFactor;
  13. //阈值为容量*负载因子和最大容量+1之间的最小值 以此值作为容量翻倍的依据(不能超过最大容量)
  14. threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
  15. //初始化一个2次幂的Entry类型数组 一个桶对应一个Entry对象
  16. table = new Entry[capacity];
  17. useAltHashing = sun.misc.VM.isBooted() &&
  18. (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
  19. init();
  20. }

2.4 Entry

  1. /**
  2. * 静态类 默认实现内部Entry接口 (接口中可定义内部接口-Map.Entry接口为Map的内部接口)
  3. * PS:JDK8中引入default,作用为在接口中定义默认方法实现
  4. */
  5. static class Entry<K,V> implements Map.Entry<K,V> {
  6. final K key;//key具有引用不可变特性
  7. V value;
  8. Entry<K,V> next;//next指向下一个:单向链表,头插入
  9. final int hash;
  10. ……
  11. }

3.HashMap的重要方法

3.1 put方法

HashMap允许存放null的key和null的value,其存储过程如下:

1.当key==null时,若存在该entry则覆盖value,否则新增key为null的entry

2.根据hash计算该entry所在桶的位置 -> 即数组下标index

3.遍历链表,若该key存在则更新value,否则新增entry (有则更新,无则新增)

  1. /**
  2. * 存放键值对
  3. * 允许存放null的key和null的value
  4. * @return key不存在返回null,否则返回旧值
  5. */
  6. public V put(K key, V value) {
  7. /**
  8. * 1.针对key为null的处理有两种方式:
  9. * 1.1从tab[0]开始向后遍历,若存在key为null的entry,则覆盖其的value
  10. * 1.2遍历完成但仍不存在key为null的entry,则新增key为null的entry
  11. * 准则:一个HashMap只允许有一个key为null的键值对
  12. * 注意:由于hash(null) = 0,因此key=null的键值对永远在tab[0]
  13. */
  14. if (key == null)
  15. return putForNullKey(value);
  16. /**
  17. * 根据key的hashCode并结合hash()算法计算出新的hash值
  18. * 目的是为了增强hash混淆 -> 因为key.hashCode()很可能不太靠谱
  19. * 而HashMap是极度依赖hash来实现元素离散的,通俗来说就是
  20. * 尽可能的让键值对可以分到不同的桶中以便快速索引
  21. */
  22. int hash = hash(key);
  23. //2.根据hash计算该元素所在桶的位置 -> 即数组下标索引
  24. int i = indexFor(hash, table.length);
  25. /**
  26. * 3.遍历链表,若该key存在则更新value,否则新增entry
  27. * 判断该key存在的依据有两个:
  28. * 1.key的hash一致
  29. * 2.key一致(引用一致或字符串一致)
  30. * put操作遵循:有则更新,无则新增
  31. */
  32. for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  33. //使用临时变量k临时存储遍历时的e.key -> 主要是为了代码复用
  34. Object k;
  35. //hash一致 && (key引用相同 或 key字符串比较相同)
  36. if (e.hash == hash && ((k = e.key) == key || key.equals(k))){
  37. //值更新
  38. V oldValue = e.value;
  39. e.value = value;
  40. //钩子方法
  41. e.recordAccess(this);
  42. //返回旧值
  43. return oldValue;
  44. }
  45. }
  46. //put操作属于结构变更操作
  47. modCount++;
  48. //无则新增
  49. addEntry(hash, key, value, i);
  50. //该key不存在就返回null -> 即新增返回null
  51. return null;
  52. }

3.2 hash方法

  1. //JDK1.7
  2. final int hash(Object k) {
  3. int h = 0;
  4. if (useAltHashing) {
  5. if (k instanceof String) {
  6. return sun.misc.Hashing.stringHash32((String) k);
  7. }
  8. h = hashSeed;
  9. }
  10. //异或就是两个数的二进制形式,按位对比,相同取0,不同取一
  11. //此算法加入了高位计算,防止低位不变,高位变化时,造成的 hash 冲突
  12. h ^= k.hashCode();
  13. h ^= (h >>> 20) ^ (h >>> 12);
  14. return h ^ (h >>> 7) ^ (h >>> 4);
  15. }
  16. //JDK1.8 扰动函数 -> 散列值优化函数
  17. static final int hash(Object key) {
  18. int h;
  19. //把一个数右移16位即丢弃低16位,就是任何小于2^16的数,右移16后结果都为0
  20. //2的16次方再右移刚好就是1 同时int最大值为32位
  21. //任何一个数,与0按位异或的结果都是这个数本身
  22. //对于非null的hash值,仅在其大于等于2^16的时候才会重新调整其值
  23. return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  24. }

3.3 indexFor方法

  1. /**
  2. * Int范围(2^32)从-2147483648到2147483648,加起来大概40亿空间,内存不能直接读取
  3. * 用之前还要先做对数组的长度取模运算,得到的余数才能用来访问数组下标
  4. * @Param h 根据hash方法得到h
  5. * @Param length 一定是2次幂
  6. */
  7. static int indexFor(int h, int length) {
  8. //2次幂-1 返回的结果的二进制为永远是都是1 比如 15 -> 1111 (16 -> 10000)
  9. //与运算 只有 1 & 1 = 1 正好相当于一个“低位掩码”
  10. //如果length-1中某一位为0,则不论h中对应位的数字为几,对应位结果都是0,这样就让两个h取到同一个结果,hash冲突
  11. //同时这个操作可以保证索引不会大于数组的大小(见开头的描述)
  12. return h & (length-1);
  13. }

3.4 addEntry方法

  1. //该方法为包访问 package java.util(本包私有性高于子类)
  2. void addEntry(int hash, K key, V value, int bucketIndex) {
  3. /**
  4. * 扩容条件:实际容量超过阈值 && 当前坐标数组非空
  5. * 有个优雅的设计在于,若bucketIndex处没有Entry对象,
  6. * 那么新添加的entry对象指向null,从而就不会有链了
  7. */
  8. if ((size >= threshold) && (null != table[bucketIndex])) {
  9. //最大容量每次都扩容一倍
  10. resize(2 * table.length);
  11. //重算hash
  12. hash = (null != key) ? hash(key) : 0;
  13. //重算index
  14. bucketIndex = indexFor(hash, table.length);
  15. }
  16. //新增Entry元素到数组的指定下标位置
  17. createEntry(hash, key, value, bucketIndex);
  18. }
  19. //该方法为包访问 package java.util
  20. void createEntry(int hash, K key, V value, int bucketIndex) {
  21. //获取数组中指定 bucketIndex 下标索引处的 Entry
  22. Entry<K,V> e = table[bucketIndex];
  23. /**
  24. * 将新创建的Entry放入 bucketIndex 索引处,
  25. * 并让新的Entry(next)指向原来的Entry形成链表
  26. * 新加入的放入链表头部 -> 类似于栈,顶部是最新的入栈元素
  27. * 对于"桶"的命名,笔者认为这词儿很形象生动:
  28. * 1.桶具有"deep深度"的属性 -> 桶深即链表长度
  29. * 2.桶的顶部永远是最新"扔"进入的元素
  30. */
  31. table[bucketIndex] = new Entry<>(hash, key, value, e);
  32. //元素数量++
  33. size++;
  34. }

3.5 关于indexFor和hash方法的进一步解读

  • hashCode返回的-2147483648到2147483648的int值,加起来大概40亿的映射空间。只要哈希函数映射比较均匀松散,一般很难出现碰撞key.hashCode()
  • 但问题是40亿长度数组,内存放不下,该散列值不能直接拿来用。用之前必须先对数组长度取模运算,得到的余数才能来访问数组下标indexFor()
  • 长度取2的整次幂,而length-1时正好相当于一个低位掩码。与操作的结果就是散列的高位全部归零,只保留低位值,用作下标访问

    10100101 11000100 00100101
    & 00000000 00000000 00001111
    00000000 00000000 00000101 //高位全部归零,只保留末四位
  • 但问题是,无论散列值再松散,但只取最后几位,碰撞也很严重。更要命的是如果散列本身做的不好,分布上成等差数列,就会出现规律性重复,这时候就需要扰动函数进行打散优化.
  • 扰动函数生效:
    扰动函数
    右位移16位(32位一半),让高半区和低半区做异或,目的是混合原始哈希码的高位和低位,以此来加大低位的随机性。而且混合后的低位包含高位的部分特征,这样高位的信息也变相保留下来。
  • 当长度非2次幂(最后一位永远是0),进行与运算(只有都为1得1,否则为0),会造成最后一位永远是0,那最后一位就无法使用,导致(1)空间的巨大浪费。同时可使用的位置比原数组长度小很多,(2)进一步增加了碰撞的几率。

3.6 存储 vs 读取

  • 存储时,根据hash算法决定其在数组中的存储位置,再根据equals方法决定其在该数组位置上的链表中的存储位置;同时HashMap会根据当前bucket的占用情况自动调整容量(超过loadFacotr则resize为原来的2倍)
  • 读取时,根据hash算法找到其在数组中的存储位置,再根据equals方法从该位置上的链表中取出该Entry。在产生碰撞的情况下,进行get时,两步的时间复杂度是O(1)+O(n)。1.8使用红黑树(O(1)+O(logn))

4.HashMap的扩容

4.1 性能参数

HashMap的性能瓶颈出现在扩容阶段,而扩容时机由两个重要属性决定:

1.initialCapacity: 初始容量,默认16

2.loadFactor: 负载因子,衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是 O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费;默认的的负载因子 0.75是对空间和时间效率的一个平衡选择;当容量超出此最大容量时, resize后的HashMap 容量是原容量的两倍

4.2 resize方法

HashMap的扩容采用的数组替换的方式:

1.先创建一个两倍于原容量的新数组

2.遍历旧数组对新数组赋值,期间会同时完成新旧索引的变更

3.新数组替换旧数组引用

4.重新计算阈值

  1. /**
  2. * Rehashes the contents of this map into a new array with a
  3. * larger capacity. This method is called automatically when the
  4. * number of keys in this map reaches its threshold.
  5. *
  6. * 目的:通过增加内部数组的长度的方式,从而保证链表中只保留很少的Entry对象,从而降低put(),remove()和get()方法的执行时间
  7. * 注意:如果两个Entry对象的键的哈希值不一样,但它们之前在同一个桶上,那么在调整以后,并不能保证它们依然在同一个桶上
  8. */
  9. void resize(int newCapacity) {
  10. /**
  11. * 使用临时拷贝,保证当前数组长度的时效性(参见JAVA的`观察者`模式实现)
  12. * 否则多线程环境下很容易造成oldCapacity的变化,
  13. * 进而导致由一系列过期数据的造成的错误
  14. */
  15. Entry[] oldTable = table;
  16. int oldCapacity = oldTable.length;
  17. //达到最大容量时禁止扩容 - 边界保护
  18. if (oldCapacity == MAXIMUM_CAPACITY) {
  19. threshold = Integer.MAX_VALUE;
  20. return;
  21. }
  22. //1.实例化一个newCapacity容量的新数组
  23. Entry[] newTable = new Entry[newCapacity];
  24. boolean oldAltHashing = useAltHashing;
  25. useAltHashing |= sun.misc.VM.isBooted() &&
  26. (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
  27. boolean rehash = oldAltHashing ^ useAltHashing;
  28. //2.遍历旧数组对新数组赋值
  29. transfer(newTable, rehash);
  30. //3.新数组替换旧数组
  31. table = newTable;
  32. //4.重新计算阈值
  33. threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
  34. }

4.3 transfer方法

  1. /**
  2. * Transfers all entries from current table to newTable.
  3. */
  4. void transfer(Entry[] newTable, boolean rehash) {
  5. int newCapacity = newTable.length;
  6. //注意:如果在新表的数组索引位置相同,则链表元素会倒置,也就是先插入最近的
  7. for (Entry<K,V> e : table) {
  8. while(null != e) {
  9. Entry<K,V> next = e.next;
  10. if (rehash) {
  11. //重新计算hash null的位置还是tab[0]不变
  12. e.hash = null == e.key ? 0 : hash(e.key);
  13. }
  14. //重新计算下标索引(主要是因为容量变化成2倍)
  15. int i = indexFor(e.hash, newCapacity);
  16. //注意:多线程环境可能由于执行次序非有序造成next引用变更赋值出错导致环形链接出现,从而造成死循环
  17. e.next = newTable[i];
  18. newTable[i] = e;
  19. e = next;
  20. }
  21. }
  22. }

5.Fail-Fast机制

5.1 错误机制

当使用迭代器的过程中有其他线程修改了map,将抛出ConcurrentModificationException

5.2 源码实现

  1. //修改计数 put、remove或clear时mount++ clear时清空
  2. transient int modCount;
  3. HashIterator() {
  4. expectedModCount = modCount;
  5. if (size > 0) {
  6. Entry[] t = table;
  7. while (index < t.length && (next = t[index++]) == null);
  8. }
  9. }
  10. final Entry<K,V> nextEntry() {
  11. //期望变更数量不匹配
  12. if (modCount != expectedModCount)
  13. throw new ConcurrentModificationException();

5.3 remove方法

5.3.1 HashMap的remove方法实现

  1. public V remove(Object key) {
  2. Entry<K,V> e = removeEntryForKey(key);
  3. return (e == null ? null : e.value);
  4. }

5.3.2 HashMap.KeySet的remove方法实现

  1. public boolean remove(Object o) {
  2. return HashMap.this.removeEntryForKey(o) != null;
  3. }

5.3.3 HashMap.HashIterator的remove方法实现

  1. public void remove() {
  2. if (current == null)
  3. throw new IllegalStateException();
  4. if (modCount != expectedModCount)
  5. throw new ConcurrentModificationException();
  6. Object k = current.key;
  7. current = null;
  8. HashMap.this.removeEntryForKey(k);
  9. //重要操作:迭代器中删除时同步了expectedModCount值与modCount相同
  10. expectedModCount = modCount;
  11. }

5.4 removeEntryForKey方法

  1. /**
  2. * Removes and returns the entry associated with the specified key
  3. * in the HashMap. Returns null if the HashMap contains no mapping
  4. * for this key.
  5. */
  6. final Entry<K,V> removeEntryForKey(Object key) {
  7. //计算hash
  8. int hash = (key == null) ? 0 : hash(key);
  9. //根据hash定位数组下标index索引
  10. int i = indexFor(hash, table.length);
  11. /**
  12. * 记录前一个enrty元素(默认从链表首元素开始)
  13. * 1.table[i] 表示链表首元素 - 即桶顶部元素
  14. * 2.prev会记录遍历时的当前entry的前一个entry
  15. */
  16. Entry<K,V> prev = table[i];
  17. //沿着链表从头到尾顺序遍历
  18. Entry<K,V> e = prev;
  19. //遍历key所在链表
  20. while (e != null) {
  21. //当前key对应entry的下一个entry
  22. Entry<K,V> next = e.next;
  23. Object k;
  24. //1.一旦key一致,即找到该key对应entry便移除并返回该entry
  25. if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
  26. //remove属于结构性更新,modCount计数+1
  27. modCount++;
  28. //实际元素数量-1
  29. size--;
  30. /**
  31. * 移除当前key对应entry,实际上就是
  32. * 通过变更前后链接将该entry从链表中移除
  33. * 1.若当前key正好位于链首,则链首指向next
  34. * 2.若当前key不位于链首,则该key之前的元素的next指向该key的下一个元素
  35. */
  36. if (prev == e)
  37. table[i] = next;
  38. else
  39. prev.next = next;
  40. //LinkedHashMap专用钩子方法
  41. e.recordRemoval(this);
  42. return e;
  43. }
  44. //2.找不到就继续往后找
  45. //记录当前key对应entry
  46. prev = e;
  47. //指向下一次循环元素
  48. e = next;
  49. }
  50. return e;
  51. }

6.HashMap的迭代

  1. Map map = new HashMap();
  2. Iterator iter = map.entrySet().iterator();
  3. while (iter.hasNext()) {
  4.  Map.Entry entry = (Map.Entry) iter.next();
  5.  Object key = entry.getKey();
  6.  Object val = entry.getValue();
  7. }

7.HashMap的常见面试题

1.什么时候会使用HashMap?他有什么特点?

  • 基于Map接口实现的Key-Value容器,允许null值,同时非有序,非同步。

2.你知道HashMap的工作原理吗?

  • 参见归纳
  • 在Java 8中,如果一个bucket中碰撞冲突的元素超过某个限制(默认是8),则使用红黑树来替换链表,从而提高速度

3.你知道get和put的原理吗?equals()和hashCode()的都有什么作用?

  • 通过对key的hashCode()进行hashing,并计算下标( n-1 & hash),从而获得buckets的位置。如果产生碰撞,则利用key.equals()方法去链表或树中去查找对应的节点

4.你知道hash的实现吗?为什么要这样实现?

  • 在Java 1.8的实现中,是通过hashCode()的高16位异或低16位实现的:(h = k.hashCode()) ^ (h >>> 16),主要是从速度、功效、质量来考虑的,这么做可以在bucket的n比较小的时候,也能保证考虑到高低bit都参与到hash的计算中,同时不会有太大的开销。
  • 使用hash还有一个好处就是 尽可能确保每个链表中的长度一致

5. 如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?

  • 如果超过了负载因子(默认0.75),则会重新resize一个原来长度两倍的HashMap,并且重新调用hash方法;同时此时很可能出现一系列问题:参见问题6

6. 你了解重新调整HashMap大小存在什么问题吗?

  • 当数据过多时,很可能出现性能瓶颈(包括rehash时间)
    使用HashMap时一定保证数量有限
  • 多线程情况下可能产生条件竞竞争从而造成死循环(具体表现在CPU接近100%)。多线程同时试着调整大小,可能导致存储在链表中的元素的次序颠倒,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历。具体死循环代码参见transfer(newTable)
    多线程环境下推荐使用ConcurrentHashMap

7. 为什么String, Interger这样的wrapper类适合作为键?

  • class具有final属性,同时重写equals()和hashCode()
  • hashCode变动会导致读取失效
  • final同时保证线程安全
    对象推荐重写equals和hashCode方法,主要用于Map存取时的对比,同时有利于减少碰撞

8.我们可以使用自定义的对象作为键吗?

  • 这是前一个问题的延伸。当然你可能使用任何对象作为键,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象时不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了
  • 典型实例就是ThreadLocal,读者可参见笔者的 并发番@ThreadLocal一文通(1.7版)

9.如何对HashMap进行排序?

  • 转换:Map -> Set -> LinkedList(存key)
  • 排序:LinkedList自行sort
  • 存储:存入有序LinkedHashMap

10.HashMap的remove陷阱?

  • 通过Iterator方式可正确遍历完成remove操作
  • 直接调用list的remove方法就会抛异常

11.为什么只允许通过iterator进行remove操作?

  • HashMap和keySet的remove方法都可以通过传递key参数删除任意的元素
  • 而iterator只能删除当前元素(current),一旦删除的元素是iterator对象中next所正在引用的,如果没有通过modCount、 expectedModCount的比较实现快速失败抛出异常,下次循环该元素将成为current指向,此时iterator就遍历了一个已移除的过期数据
  • 之所以推荐迭代器remove的根本原因在于只有迭代器的remove方法中实现了变更时于modCount的同步工作
    expectedModCount = modCount;

12.如果是遍历过程中增加或修改数据呢?

  • 增加或修改数据只能通过Map的put方法实现,在遍历过程中修改数据可以,但如果增加新key就会在下次循环时抛异常,因为在添加新key时modCount也会自增(迭代器只实现了remove方法也是原因之一)

集合番@HashMap一文通(1.7版)黄志鹏kira 创作,采用 知识共享 署名-非商业性使用 4.0 国际 许可协议 进行许可。

本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注