JAVA代码分析,语法分析java

　　00-1010 1.HashMap数据结构2。HashMap特性3。HashMap java集合容器类中的put方法流分为两类：集合和Map。collection类的子接口是Set、List和Queue，map类的子接口是SortedMap。例如，ArrayList和HashMap的继承和实现关系如下

　　00-1010在jdk1.8中，底层数据结构是“数组链表的红黑树”。事实上，HashMap的底层实现仍然是一个数组，但是数组的每一项都是一个链，如下所示

　　当链表过长时，会严重影响HashMap的性能。红黑树的搜索时间复杂度是O(logn)，而链表是O(n)。所以jdk1.8引入红黑树进一步优化，满足一定条件时链表和红黑树进行转换：

　　当链表转换为红黑树时，会判断如果当前数组长度小于64，则先扩展数组，而不是转换为红黑树，以减少搜索时间；当链表超过8，数组长度超过64，就会变成红黑树；

目录

哈希表访问顺序错误；而且k和v都可以是null，但是k只能是null；当阈值大于8，数组长度大于64时，链表将被转换为红黑树。变成红黑树的目的是为了提高搜索速度。

　　链表转换为红黑树的原因：如果红黑树出现在数组很小的时候，会降低效率，而红黑树需要左右手变换颜色来保持平衡。当同事数组长度小于64时，搜索速度也更快。

　　之所以默认加载因子为0.75:HashMap中的threadhold是HashMap可以容纳键值对的最大值。计算公式为threadhold=leng*loadFactory。在定义了数组的长度之后，加载因子越大，它可以容纳的键值对的数量就越多。loadFactory越接近1，数组中存储的数据越密集，链表长度就会越长，我们的查询效率就会越低，在添加数据时，哈希冲突的概率就会越高。负载越接近0。数组中存储的数据越稀少，0.75是空间和时间效率的平衡选择。它是经过多次计算的可靠值。

　　哈希值计算：hashCode方法是Object中的方法，所有类都可以使用。首先在底层调用hashCode方法生成初始哈希值h1，然后h1无符号右移16位得到h2，然后h1和h2按位异或得到最终哈希值h3，然后h3和length-1按位and得到哈希表索引。

　　00-1010源代码如下

　　public V put(K key，V value) { return putVal(hash(key)，key，value，false，true)；} /** *实现Map.put和相关方法* * @param hash键的hash值* @param key键* @param值要放置的值* @param onlyIfAbsent如果为true，不更改现有值* @param evict如果为false，则表处于创建模式。* @返回上一个值，如果没有则返回null */final V putVal(int hash，K key，V value，boolean onlyIfAbsent，boolean evict) { NodeK，V[]tab；NodeK，V p；int n，I；if((tab=table)==null (n=tab . length)==0)n=(tab=resize())。长度；if((p=tab[I=(n-1)hash])==null)tab[I]=new node(hash，key，value，null)；else { NodeK，V e；K kif(p . hash==hash((k=p . key)==key (key！=空键。

　　equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }首先根据key的值计算hash值，找到该元素在数组中存储的下标；

　　若数组是空的，则调用resize进行初始化；

　　若没有hash冲突，则直接放在对应的数组下标里；

　　若发生hash冲突了，且key已经存储，就覆盖掉value；

　　若发生hash冲突后是链表结构，就判断该链表是否大于8，若大于8且数组容量小于64，就进行扩容；若链表节点数量大于8且数组容量大于64，则将这个结构转换位红黑树；否则链表插入键值对，若key存在则覆盖掉value；

　　若hash冲突后，发现该节点是红黑树，就将这个节点挂在数上；

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { 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 } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (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"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }

hashMap在容量超过负载因子后就会扩容，将hashMap的大小扩大为原来数组的两倍。

　　HashMap是非线程安全的，在put的时候，插入的元素超过了容量的范围就会进行扩容操作rehash，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现在同一数组下用链表表示，造成闭环，导致在get操作时出现死循环，所以hashMap是线程不安全的。

　　继续理解源码的设计妙处。

　　到此这篇关于Java详细分析讲解HashMap的文章就介绍到这了,更多相关Java HashMap内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。