HashMap源码详解一篇就够 HashMap源码详解一篇就够

文章图片
image.png 概述 HashMap是基于哈希表(散列表)，实现Map接口的双列集合，数据结构是“链表散列”，也就是数组+链表，key唯一的value可以重复，允许存储null 键null 值，元素无序。
哈希表数组：一段连续控件存储数据，指定下标的查找，时间复杂度O(1),通过给定值查找，需要遍历数组，自已对比复杂度为O（n）二分查找插值查找，复杂度为O(logn)
线性链表：增删除仅处理结点，时间复杂度O(1)查找需要遍历也就是O(n)
二叉树：对一颗相对平衡的有序二叉树，对其进行插入，查找，删除，平均复杂度O(logn)
哈希表：哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)哈希表的主干就是数组
hash冲突如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式
链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么对于查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好
HashMap数据结构
文章图片
image.png HashMap的底层就是一个数组，数组中每一项有事一个链表，当新建一个HashMap时候，就会初始化一个数组，查看源码如下，直接看重点，table = new Entry[capacity]; 创建一个Entry数组，也就是上面的table ,这个Entry结构就是static的包含key value 还有一个next的指针，指向下一个元素的引用，也就构成了链表

public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); init(); }

entry结构：

static class Entry implements Map.Entry { final K key; V value; Entry next; final int hash; …… }

HashMap存储调用put 方法时候，如果key存在key不会覆盖，新的value会替代旧的value，返回旧的value; 如果key不存在，该方法返回null
看它的源码，调用put时候，根据key的hashCode重新计算hash值，根据hash值得到这个元素在数组中的位置也就是下标，如果数组在该位置上已有其他元素，那么在这个位置上的元素将以链表的形式存放，新加入的在立案表头，先加入的在尾部

public V put(K key, V value) { //其允许存放null的key和null的value，当其key为null时，调用putForNullKey方法，放入到table[0]的这个位置 if (key == null) return putForNullKey(value); //通过调用hash方法对key进行哈希，得到哈希之后的数值。该方法实现可以通过看源码，其目的是为了尽可能的让键值对可以分不到不同的桶中 int hash = hash(key); //根据上一步骤中求出的hash得到在数组中是索引i int i = indexFor(hash, table.length); //如果i处的Entry不为null，则通过其next指针不断遍历e元素的下一个元素。 for (Entry e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = https://www.it610.com/article/e.value; e.value = value; e.recordAccess(this); return oldValue; } }modCount++; addEntry(hash, key, value, i); return null; }

HashMap的读取

public V get(Object key) { if (key == null) return getForNullKey(); Entry entry = getEntry(key); return null == entry ? null : entry.getValue(); }final Entry getEntry(Object key) { int hash = (key == null) ? 0 : hash(key); for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }

get()方法也会是首先计算key的 hashCode 找到数组中对应位置的某一元素，通过key的equals方法在对应位置的链表中找到要的元素，
key(hashcode)-->hash-->indexFor-->最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过equals判断就可以。其实不然，试想一下，如果传入的key对象重写了equals方法却没有重写hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用equals判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null，后面的例子会做出进一步解释。
hash算法 hash(int h)方法是根据key的hashCode重新计算一次散列。此算法加入了高位计算，防止低位不变，高位变化时，造成的hash冲突

final int hash(Object k) { int h = 0; if (useAltHashing) { if (k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h = hashSeed; } //得到k的hashcode值 h ^= k.hashCode(); //进行计算 h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }

我们根据hash值获得在数组中的位置，我们希望hashmap里面元素位置尽量分布均匀，尽量是的没个位置上的元素数量只有一个每当hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要读取的，不用再遍历链表，提神效率 HashMap的容量 【HashMap源码详解一篇就够】任意对象，它的hashCode()返回值相同，那么程序调用hash(int h)方法所计算得到的hash码值总是相同的，为了让他的hash值得到位置分布更均匀，可以对他 % 运算，但是%运算性能肯定是没有位与运算举个例子比如我们的h是10 h% 4=2; 使用10&（4-1）也就是1010&0011 = 0010 也就是2，但是我们计算机存储是二进制，所以性能高不少！

static int indexFor(int h, int length) { return h & (length-1); }

HashMap底层数组的长度总是 2 的 n 次方,通过这个indexFor方法得到保存位
为什么是2的n次方假如是长度15 ，而我们的h 是8 和9 2种情况，那么forIndex计算如下
1000 1001
1110 1110
——————————————
1000 1000
结果是一样的，也就是在数组中一个位置上那么查询的时候就要遍历链表得到8或者9，降低查询效率。同时，长度15时候，hash值会和 1110 与运算，最后一位是1的比如0001，0011,0111,1011.。。。这几个位置算下来一直都是尾数是0 ，这样就相当于这几个位置存不到数据，造成空间浪费，可用长度，变小了也就意味着增加了碰撞的几率，减慢查询效率，而当长度是2的n次方时候，比如1111 11111 都能保证得到和原来hash低位相同，也就是扩容后只有一个位差异，多出来最左边位的1 这样只要对应左边的哪一个差异位为0，就能保证得到新的数组索引和老的数组索引一直，这样数据在数组的分布比较均匀，也就是说减少碰撞的几率，减少了链表的遍历，提升效率
h: 0 1000
16的length-1 0 1110
32的length-1 1 1110
————————————————
h的 01000 的第一个0为0就能保证一直，为1没办法！
最终存储流程：

文章图片
试试.png HashMap的resize（rehash）当 HashMap 中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的，所以为了提高查询的效率，就要对HashMap的数组进行扩容，在HashMap数组扩容之后，最消耗性能的点是：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是 resize（rehash）
loadFactor指的是负载因子 HashMap能够承受住自身负载（大小或容量）的因子，loadFactor的默认值为 0.75认情况下，数组大小为 16，那么当HashMap中元素个数超过 160.75=12 的时候，就把数组的大小扩展为 216=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知 HashMap 中元素的个数，那么预设元素的个数能够有效的提高 HashMap 的性能
负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是 O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费
HashMap不是线程安全的总结 HashMap在底层将key-value当成一个整体进行处理，这个整体就是一个Entry对象。HashMap底层采用一个 Entry[]数组来保存所有的key-value，当需要存储一个Entry对象时，会根据 hash 算法来决定其在数组中的存储位置，在根据equals方法决定其在该数组位置上的链表中的存储位置；当需要取出一个Entry时，也会根据hash算法找到其在数组中的存储位置，再根据equals方法从该位置上的链表中取出该Entry
常见面试题当两个对象的hashcode相同会发生什么？ hashcode相同，说明两个对象HashMap数组的同一位置上，接着HashMap会遍历链表中的每个元素，通过key的equals方法来判断是否为同一个key，如果是同一个key，则新的value会覆盖旧的value，并且返回旧的value。如果不是同一个key，则存储在该位置上的链表的链头
如果两个键的hashcode相同，你如何获取值对象？遍历HashMap链表中的每个元素，并对每个key进行hash计算，最后通过get方法获取其对应的值对象
你了解重新调整HashMap大小存在什么问题吗？当多线程的情况下，可能产生条件竞争。当重新调整HashMap大小的时候，确实存在条件竞争，如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的数组位置的时候，HashMap并不会将元素放在LinkedList的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了