网站建设百度文库,个人主页免费网站,玉山县建设局网站,网站域名实名认证怎么做HashMap是面试中经常问到的一个知识点,也是判断一个候选人基础是否扎实的标准之一。可见HashMap的掌握是多重要。
一、HashMap源码分析
1、构造函数
让我们先从构造函数说起#xff0c;HashMap有四个构造方法#xff0c;别慌
1.1 HashMap() // 1.无参构造方法、// 构造一…HashMap是面试中经常问到的一个知识点,也是判断一个候选人基础是否扎实的标准之一。可见HashMap的掌握是多重要。
一、HashMap源码分析
1、构造函数
让我们先从构造函数说起HashMap有四个构造方法别慌
1.1 HashMap() // 1.无参构造方法、// 构造一个空的HashMap初始容量为16负载因子为0.75public HashMap() { this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted}
无参构造方法就没什么好说的了。
1.2 HashMap(int initialCapacity) // 2.构造一个初始容量为initialCapacity负载因子为0.75的空的HashMappublic HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);}
HashMap(int initialCapacity) 这个构造方法调用了1.3中的构造方法。
1.3 HashMap(int initialCapacity, float loadFactor) // 3.构造一个空的初始容量为initialCapacity负载因子为loadFactor的HashMappublic 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); this.loadFactor loadFactor; this.threshold tableSizeFor(initialCapacity);} //最大容量//static final int MAXIMUM_CAPACITY 1 30;
当指定的初始容量 0时抛出IllegalArgumentException异常当指定的初始容量 MAXIMUM_CAPACITY时就让初始容量 MAXIMUM_CAPACITY。当负载因子小于0或者不是数字时抛出IllegalArgumentException异常。
设定threshold。 这个threshold capacity * load factor 。当HashMap的size到了threshold时就要进行resize也就是扩容。
tableSizeFor()的主要功能是返回一个比给定整数大且最接近的2的幂次方整数如给定10返回2的4次方16.
我们进入tableSizeFor(int cap)的源码中看看 //Returns a power of two size for the given target capacity.static final int tableSizeFor(int cap) { int n cap - 1;n | n 1;n | n 2;n | n 4;n | n 8;n | n 16; return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;}
note HashMap要求容量必须是2的幂。
首先int n cap -1是为了防止cap已经是2的幂时执行完后面的几条无符号右移操作之后返回的capacity是这个cap的2倍因为cap已经是2的幂了就已经满足条件了。 如果不懂可以往下看完几个无符号移位后再回来看。建议自己在纸上画一下 如果n这时为0了经过了cap-1之后则经过后面的几次无符号右移依然是0最后返回的capacity是1最后有个n1的操作。这里只讨论n不等于0的情况。
以16位为例假设开始时 n 为 0000 1xxx xxxx xxxx x代表不关心0还是1 第一次右移 n | n 1; 由于n不等于0则n的二进制表示中总会有一bit为1这时考虑最高位的1。通过无符号右移1位则将最高位的1右移了1位再做或操作使得n的二进制表示中与最高位的1紧邻的右边一位也为1如0000 11xx xxxx xxxx 。 第二次右移 n | n 2; 注意这个n已经经过了n | n 1; 操作。此时n为0000 11xx xxxx xxxx 则n无符号右移两位会将最高位两个连续的1右移两位然后再与原来的n做或操作这样n的二进制表示的高位中会有4个连续的1。如0000 1111 xxxx xxxx 。 第三次右移 n | n 4; 这次把已经有的高位中的连续的4个1右移4位再做或操作这样n的二进制表示的高位中会有8个连续的1。如0000 1111 1111 xxxx 。
第。。。你还忍心让我继续推么相信聪明的你已经想出来了容量最大也就是32位的正数所以最后一次 n | n 16; 可以保证最高位后面的全部置为1。当然如果是32个1的话此时超出了MAXIMUM_CAPACITY 所以取值到 MAXIMUM_CAPACITY 。
这里我从别人的文章当一个别人的图片懒得画了 tableSizeFor示例图注意得到的这个capacity却被赋值给了threshold。 这里我和这篇博客的博主开始的想法一样认为应该这么写this.threshold tableSizeFor(initialCapacity) * this.loadFactor; 因为这样子才符合threshold的定义threshold capacity * load factor 。但是请注意在构造方法中并没有对table这个成员变量进行初始化table的初始化被推迟到了put方法中在put方法中会对threshold重新计算 。
我说一下我在理解这个tableSizeFor函数中间遇到的坑吧我在想如果n-1时的情况因为初始容量可以传进来0。我将n -1 和下面几条运算一起新写了个测试程序发现输出都是 -1。 这是因为计算机中数字是由补码存储的-1的补码是 0xffffffff。所以无符号右移之后再进行或运算之后还是 -1。 那我想如果就无符号右移呢 比如-110。听我娓娓道来32个1无符号右移10位后高10位为0低22位为1此时这个数变成了正数由于正数的补码和原码相同所以就变成了0x3FFFFF即10进制的4194303。真刺激。
好开森这个构造方法我们算是拿下了。怎么样我猜你现在一定很激动Heyold Fe这才刚开始。接下来看最后一个构造方法。
1.4 HashMap(Map? extends K, ? extends V m) // 4. 构造一个和指定Map有相同mappings的HashMap初始容量能充足的容下指定的Map,负载因子为0.75public HashMap(Map? extends K, ? extends V m) { this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}
套路直接看 putMapEntries(m,false) 。源码如下 /*** 将m的所有元素存入本HashMap实例中*/final void putMapEntries(Map? extends K, ? extends V m, boolean evict) { //得到 m 中元素的个数int s m.size(); //当 m 中有元素时则需将map中元素放入本HashMap实例。if (s 0) { // 判断table是否已经初始化如果未初始化则先初始化一些变量。table初始化是在put时if (table null) { // pre-size// 根据待插入的map 的 size 计算要创建的 HashMap 的容量。float ft ((float)s / loadFactor) 1.0F; int t ((ft (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY); // 把要创建的 HashMap 的容量存在 threshold 中if (t threshold)threshold tableSizeFor(t);} // 如果table初始化过因为别的函数也会调用它所以有可能HashMap已经被初始化过了。// 判断待插入的 map 的 size,若 size 大于 threshold则先进行 resize()进行扩容else if (s threshold)resize(); //然后就开始遍历 带插入的 map 将每一个 Key ,Value 插入到本HashMap实例。for (Map.Entry? extends K, ? extends V e : m.entrySet()) {K key e.getKey();V value e.getValue(); // put(K,V)也是调用 putVal 函数进行元素的插入putVal(hash(key), key, value, false, evict);}}}
介绍putVal方法前说一下HashMap的几个重要的成员变量 /*** The table, initialized on first use, and resized as* necessary. When allocated, length is always a power of two.* (We also tolerate length zero in some operations to allow* bootstrapping mechanics that are currently not needed.)*///实际存储keyvalue的数组只不过keyvalue被封装成Node了transient NodeK,V[] table; /*** The number of key-value mappings contained in this map.*/transient int size; /*** The number of times this HashMap has been structurally modified* Structural modifications are those that change the number of mappings in* the HashMap or otherwise modify its internal structure (e.g.,* rehash). This field is used to make iterators on Collection-views of* the HashMap fail-fast. (See ConcurrentModificationException).*/transient int modCount; /*** The next size value at which to resize (capacity * load factor).** serial*/// (The javadoc description is true upon serialization.// Additionally, if the table array has not been allocated, this// field holds the initial array capacity, or zero signifying// DEFAULT_INITIAL_CAPACITY.)//因为 tableSizeFor(int) 返回值给了thresholdint threshold; /*** The load factor for the hash table.** serial*/final float loadFactor;
其实就是哈希表。HashMap使用链表法避免哈希冲突相同hash值当链表长度大于TREEIFY_THRESHOLD默认为8时将链表转换为红黑树当然小于UNTREEIFY_THRESHOLD默认为6时又会转回链表以达到性能均衡。 我们看一张HashMap的数据结构数组链表红黑树 就更能理解table了
HashMap的数据结构再回到putMapEntries函数中如果table为null那么这时就设置合适的threshold如果不为空并且指定的map的sizethreshold那么就resize()。然后把指定的map的所有KeyValue通过putVal添加到我们创建的新的map中。
putVal中传入了个hash(key)那我们就先来看看hash(key):
/*** key 的 hash值的计算是通过hashCode()的高16位异或低16位实现的(h k.hashCode()) ^ (h 16)* 主要是从速度、功效、质量来考虑的这么做可以在数组table的length比较小的时候* 也能保证考虑到高低Bit都参与到Hash的计算中同时不会有太大的开销*/static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16);}
异或运算(h key.hashCode()) ^ (h 16)
原 来 的 hashCode : 1111 1111 1111 1111 0100 1100 0000 1010 移位后的hashCode: 0000 0000 0000 0000 1111 1111 1111 1111 进行异或运算 结果1111 1111 1111 1111 1011 0011 1111 0101
这样做的好处是可以将hashcode高位和低位的值进行混合做异或运算而且混合后低位的信息中加入了高位的信息这样高位的信息被变相的保留了下来。掺杂的元素多了那么生成的hash值的随机性会增大。
刚才我们漏掉了resize()和putVal() 两个函数现在我们按顺序分析一波
首先resize() ,先看一下哪些函数调用了resize()从而在整体上有个概念
调用了resize的函数接下来上源码 final NodeK,V[] resize() { // 保存当前tableNodeK,V[] oldTab table; // 保存当前table的容量int oldCap (oldTab null) ? 0 : oldTab.length; // 保存当前阈值int oldThr threshold; // 初始化新的table容量和阈值 int newCap, newThr 0; /*1. resize函数在size threshold时被调用。oldCap大于 0 代表原来的 table 表非空oldCap 为原表的大小oldThrthreshold 为 oldCap × load_factor*/if (oldCap 0) { // 若旧table容量已超过最大容量更新阈值为Integer.MAX_VALUE最大整形值这样以后就不会自动扩容了。if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE; return oldTab;} // 容量翻倍使用左移效率更高else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) // 阈值翻倍newThr oldThr 1; // double threshold} /*2. resize函数在table为空被调用。oldCap 小于等于 0 且 oldThr 大于0代表用户创建了一个 HashMap但是使用的构造函数为 HashMap(int initialCapacity, float loadFactor) 或 HashMap(int initialCapacity)或 HashMap(Map? extends K, ? extends V m)导致 oldTab 为 nulloldCap 为0 oldThr 为用户指定的 HashMap的初始容量。*/else if (oldThr 0) // initial capacity was placed in threshold//当table没初始化时threshold持有初始容量。还记得threshold tableSizeFor(t)么;newCap oldThr; /*3. resize函数在table为空被调用。oldCap 小于等于 0 且 oldThr 等于0用户调用 HashMap()构造函数创建的 HashMap所有值均采用默认值oldTabTable表为空oldCap为0oldThr等于0*/else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);} // 新阈值为0if (newThr 0) { float ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold newThr; SuppressWarnings({rawtypes,unchecked}) // 初始化tableNodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab; if (oldTab ! null) { // 把 oldTab 中的节点 reHash 到 newTab 中去for (int j 0; j oldCap; j) {NodeK,V e; if ((e oldTab[j]) ! null) {oldTab[j] null; // 若节点是单个节点直接在 newTab 中进行重定位if (e.next null)newTab[e.hash (newCap - 1)] e; // 若节点是 TreeNode 节点要进行 红黑树的 rehash 操作else if (e instanceof TreeNode)((TreeNodeK,V)e).split(this, newTab, j, oldCap); // 若是链表进行链表的 rehash 操作else { // preserve orderNodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next; // 将同一桶中的元素根据(e.hash oldCap)是否为0进行分割代码后有图解可以回过头再来看分成两个不同的链表完成rehashdo {next e.next; // 根据算法 e.hash oldCap 判断节点位置rehash 后是否发生改变//最高位0这是索引不变的链表。if ((e.hash oldCap) 0) { if (loTail null)loHead e; elseloTail.next e;loTail e;} //最高位1 这是索引发生改变的链表else { if (hiTail null)hiHead e; elsehiTail.next e;hiTail e;}} while ((e next) ! null); if (loTail ! null) { // 原bucket位置的尾指针不为空(即还有node) loTail.next null; // 链表最后得有个nullnewTab[j] loHead; // 链表头指针放在新桶的相同下标(j)处} if (hiTail ! null) {hiTail.next null; // rehash 后节点新的位置一定为原来基础上加上 oldCap具体解释看下图newTab[j oldCap] hiHead;}}}}} return newTab;}
}
引自美团点评技术博客。我们使用的是2次幂的扩展(指长度扩为原来2倍)所以元素的位置要么是在原位置要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思n为table的长度图a表示扩容前的key1和key2两种key确定索引位置的示例图b表示扩容后key1和key2两种key确定索引位置的示例其中hash1是key1对应的哈希与高位运算结果。
hashMap 1.8 哈希算法例图1元素在重新计算hash之后因为n变为2倍那么n-1的mask范围在高位多1bit(红色)因此新的index就会发生这样的变化
hashMap 1.8 哈希算法例图2因此我们在扩充HashMap的时候只需要看看原来的hash值新增的那个bit是1还是0就好了是0的话索引没变是1的话索引变成“原索引oldCap”可以看看下图为16扩充为32的resize示意图
jdk1.8 hashMap扩容例图什么时候扩容通过HashMap源码可以看到是在put操作时即向容器中添加元素时判断当前容器中元素的个数是否达到阈值当前数组长度乘以加载因子的值的时候就要自动扩容了。
扩容(resize)其实就是重新计算容量而这个扩容是计算出所需容器的大小之后重新定义一个新的容器将原来容器中的元素放入其中。
resize()告一段落接下来看 putVal() 。
上源码 //实现put和相关方法。final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i; //如果table为空或者长度为0则resize()if ((tab table) null || (n tab.length) 0)n (tab resize()).length; //确定插入table的位置算法是(n - 1) hash在n为2的幂时相当于取摸操作。找到key值对应的槽并且是第一个直接加入if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null); //在table的i位置发生碰撞有两种情况1、key值是一样的替换value值//2、key值不一样的有两种处理方式2.1、存储在i位置的链表2.2、存储在红黑树中else {NodeK,V e; K k; //第一个node的hash值即为要加入元素的hashif (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p; //2.2else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); //2.1else { //不是TreeNode,即为链表,遍历链表for (int binCount 0; ; binCount) { ///链表的尾端也没有找到key值相同的节点则生成一个新的Node,//并且判断链表的节点个数是不是到达转换成红黑树的上界达到则转换成红黑树。if ((e p.next) null) { // 创建链表节点并插入尾部p.next newNode(hash, key, value, null); 超过了链表的设置长度8就转换成红黑树if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash); break;} if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break;p e;}} //如果e不为空就替换旧的oldValue值if (e ! null) { // existing mapping for keyV oldValue e.value; if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e); return oldValue;}}modCount; if (size threshold)resize();afterNodeInsertion(evict); return null;} 注hash 冲突发生的几种情况 1.两节点key 值相同hash值一定相同导致冲突 2.两节点key 值不同由于 hash 函数的局限性导致hash 值相同冲突 3.两节点key 值不同hash 值不同但 hash 值对数组长度取模后相同冲突 相比put方法get方法就比较简单这里就不说了。
1.7和1.8的HashMap的不同点
1JDK1.7用的是头插法而JDK1.8及之后使用的都是尾插法那么为什么要这样做呢因为JDK1.7是用单链表进行的纵向延伸当采用头插法就是能够提高插入的效率但是也会容易出现逆序且环形链表死循环问题。但是在JDK1.8之后是因为加入了红黑树使用尾插法能够避免出现逆序且链表死循环的问题。
2扩容后数据存储位置的计算方式也不一样 在JDK1.7的时候是直接用hash值和需要扩容的二进制数进行这里就是为什么扩容的时候为啥一定必须是2的多少次幂的原因所在因为如果只有2的n次幂的情况时最后一位二进制数才一定是1这样能最大程度减少hash碰撞hash值 length-1 。 而在JDK1.8的时候直接用了JDK1.7的时候计算的规律也就是扩容前的原始位置扩容的大小值JDK1.8的计算方式而不再是JDK1.7的那种异或的方法。但是这种方式就相当于只需要判断Hash值的新增参与运算的位是0还是1就直接迅速计算出了扩容后的储存方式。
3JDK1.7的时候使用的是数组 单链表的数据结构。但是在JDK1.8及之后时使用的是数组链表红黑树的数据结构当链表的深度达到8的时候也就是默认阈值就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从ON变成OlogN提高了效率。
HashMap为什么是线程不安全的
HashMap 在并发时可能出现的问题主要是两方面 put的时候导致的多线程数据不一致 比如有两个线程A和B首先A希望插入一个key-value对到HashMap中首先计算记录所要落到的 hash桶的索引坐标然后获取到该桶里面的链表头结点此时线程A的时间片用完了而此时线程B被调度得以执行和线程A一样执行只不过线程B成功将记录插到了桶里面假设线程A插入的记录计算出来的 hash桶索引和线程B要插入的记录计算出来的 hash桶索引是一样的那么当线程B成功插入之后线程A再次被调度运行时它依然持有过期的链表头但是它对此一无所知以至于它认为它应该这样做如此一来就覆盖了线程B插入的记录这样线程B插入的记录就凭空消失了造成了数据不一致的行为。 resize而引起死循环 这种情况发生在HashMap自动扩容时当2个线程同时检测到元素个数超过 数组大小 × 负载因子。此时2个线程会在put()方法中调用了resize()两个线程同时修改一个链表结构会产生一个循环链表JDK1.7中会出现resize前后元素顺序倒置的情况。接下来再想通过get()获取某一个元素就会出现死循环。
HashMap和HashTable的区别
HashMap和Hashtable都实现了Map接口但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有线程安全性同步(synchronization)以及速度。 HashMap几乎可以等价于Hashtable除了HashMap是非synchronized的并可以接受null(HashMap可以接受为null的键值(key)和值(value)而Hashtable则不行)。 HashMap是非synchronized而Hashtable是synchronized这意味着Hashtable是线程安全的多个线程可以共享一个Hashtable而如果没有正确的同步的话多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap它是HashTable的替代比HashTable的扩展性更好。 另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构增加或者移除元素将会抛出ConcurrentModificationException但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为要看JVM。这条同样也是Enumeration和Iterator的区别。 由于Hashtable是线程安全的也是synchronized所以在单线程环境下它比HashMap要慢。如果你不需要同步只需要单一线程那么使用HashMap性能要好过Hashtable。 HashMap不能保证随着时间的推移Map中的元素次序是不变的。
需要注意的重要术语 sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。 Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator然后其它的线程试图“结构上”更改集合对象将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改再调用set()方法将会抛出IllegalArgumentException异常。 结构上的更改指的是删除或者插入一个元素这样会影响到map的结构。
