博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
HashMap解惑
阅读量：5959 次
发布时间：2019-06-19

本文共 10450 字，大约阅读时间需要 34 分钟。

 HashMap中有一些我们容易忽视的点

1. 关于key的hash和equals

Java代码  
  1. public V put(K key, V value) {  
  2.         if (table == EMPTY_TABLE) {  
  3.             inflateTable(threshold);  
  4.         }  
  5.         if (key == null)  
  6.             return putForNullKey(value);  
  7.         int hash = hash(key);  
  8.         int i = indexFor(hash, table.length);  
  9.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
  10.             Object k;  
  11.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
  12.                 V oldValue = e.value;  
  13.                 e.value = value;  
  14.                 e.recordAccess(this);  
  15.                 return oldValue;  
  16.             }  
  17.         }  
  18.   
  19.         modCount++;  
  20.         addEntry(hash, key, value, i);  
  21.         return null;  
  22.     }  

 由上述代码知道，hash值是用来确定bucketIndex，equals是用来和链表上的值比较，因此对于key是自定义的类，强烈建议重写hashCode和equals方法。此处也是容易引起内存泄露的点。

下面摘抄一段JDK里面的注释，

Java代码  
  1. /** 
  2.      * Returns a hash code value for the object. This method is 
  3.      * supported for the benefit of hash tables such as those provided by 
  4.      * {@link java.util.HashMap}. 
  5.      * <p> 
  6.      * The general contract of {@code hashCode} is: 
  7.      * <ul> 
  8.      * <li>Whenever it is invoked on the same object more than once during 
  9.      *     an execution of a Java application, the {@code hashCode} method 
  10.      *     must consistently return the same integer, provided no information 
  11.      *     used in {@code equals} comparisons on the object is modified. 
  12.      *     This integer need not remain consistent from one execution of an 
  13.      *     application to another execution of the same application. 
  14.      * <li>If two objects are equal according to the {@code equals(Object)} 
  15.      *     method, then calling the {@code hashCode} method on each of 
  16.      *     the two objects must produce the same integer result. 
  17.      * <li>It is <em>not</em> required that if two objects are unequal 
  18.      *     according to the {@link java.lang.Object#equals(java.lang.Object)} 
  19.      *     method, then calling the {@code hashCode} method on each of the 
  20.      *     two objects must produce distinct integer results.  However, the 
  21.      *     programmer should be aware that producing distinct integer results 
  22.      *     for unequal objects may improve the performance of hash tables. 
  23.      * </ul> 
  24.      * <p> 
  25.      * As much as is reasonably practical, the hashCode method defined by 
  26.      * class {@code Object} does return distinct integers for distinct 
  27.      * objects. (This is typically implemented by converting the internal 
  28.      * address of the object into an integer, but this implementation 
  29.      * technique is not required by the 
  30.      * Java<font size="-2"><sup>TM</sup></font> programming language.) 
  31.      * 
  32.      * @return  a hash code value for this object. 
  33.      * @see     java.lang.Object#equals(java.lang.Object) 
  34.      * @see     java.lang.System#identityHashCode 
  35.      */  
  36.     public native int hashCode();  

 

 

2. rehash的条件

Java代码  
  1. void addEntry(int hash, K key, V value, int bucketIndex) {  
  2.         if ((size >= threshold) && (null != table[bucketIndex])) {  
  3.             resize(2 * table.length);  
  4.             hash = (null != key) ? hash(key) : 0;  
  5.             bucketIndex = indexFor(hash, table.length);  
  6.         }  
  7.   
  8.         createEntry(hash, key, value, bucketIndex);  
  9.     }  

 if条件告诉我们rehash的条件要同时满足两个：map中元素个数不小于阀值即容量*负载因子，对应的bucketIndex处有元素。

 另外，如下代码作备忘，

Java代码  
  1. static int indexFor(int h, int length) {  
  2.         // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";  
  3.         return h & (length-1);  
  4.     }  

 

3. 可以插入(null, null)吗

Java代码  
  1. Map<String, String> map = new HashMap<String, String>();  
  2.         map.put(null, null);  
  3.         System.out.println(map.size()); // 1  
  4.   
  5. private V putForNullKey(V value) {  
  6.         for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
  7.             if (e.key == null) {  
  8.                 V oldValue = e.value;  
  9.                 e.value = value;  
  10.                 e.recordAccess(this);  
  11.                 return oldValue;  
  12.             }  
  13.         }  
  14.         modCount++;  
  15.         addEntry(0, null, value, 0); // hash = 0, bucketIndex = 0  
  16.         return null;  
  17.     }  

注意，Hashtable和ConcurrentHashMap进行put时若value为null，将抛出NullPointerException。 

 

4. table默认初始大小 - 16

Java代码  
  1. public HashMap(int initialCapacity, float loadFactor) {  
  2.         // ...  
  3.   
  4.         this.loadFactor = loadFactor; // 0.75  
  5.         threshold = initialCapacity; // 16  
  6.         init(); // nothing  
  7.     }  
  8.   
  9. public V put(K key, V value) {  
  10.         if (table == EMPTY_TABLE) {  
  11.             inflateTable(threshold);  
  12.         }  
  13.         // ...  
  14. }  
  15.   
  16. private void inflateTable(int toSize) {  
  17.         // Find a power of 2 >= toSize  
  18.         int capacity = roundUpToPowerOf2(toSize); // 16  
  19.   
  20.         threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);  
  21.         table = new Entry[capacity];  
  22.         initHashSeedAsNeeded(capacity);  
  23.     }  
  24.   
  25. private static int roundUpToPowerOf2(int number) {  
  26.         // assert number >= 0 : "number must be non-negative";  
  27.         return number >= MAXIMUM_CAPACITY  
  28.                 ? MAXIMUM_CAPACITY  
  29.                 : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;  
  30.     }  

 

5. 关于HashMap里的hash(Object key)方法

Java代码  
  1. final int hash(Object k) {  
  2.         int h = hashSeed;  
  3.         if (0 != h && k instanceof String) {  
  4.             return sun.misc.Hashing.stringHash32((String) k);  
  5.         }  
  6.   
  7.         h ^= k.hashCode();  
  8.   
  9.         // This function ensures that hashCodes that differ only by  
  10.         // constant multiples at each bit position have a bounded  
  11.         // number of collisions (approximately 8 at default load factor).  
  12.         h ^= (h >>> 20) ^ (h >>> 12);  
  13.         return h ^ (h >>> 7) ^ (h >>> 4);  
  14.     }  
  15.   
  16. /** 
  17.      * Initialize the hashing mask value. We defer initialization until we 
  18.      * really need it. 
  19.      */  
  20.     final boolean initHashSeedAsNeeded(int capacity) {  
  21.         boolean currentAltHashing = hashSeed != 0;  
  22.         boolean useAltHashing = sun.misc.VM.isBooted() &&  
  23.                 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);  
  24.         boolean switching = currentAltHashing ^ useAltHashing;  
  25.         if (switching) {  
  26.             hashSeed = useAltHashing  
  27.                 ? sun.misc.Hashing.randomHashSeed(this)  
  28.                 : 0;  
  29.         }  
  30.         return switching;  
  31.     }  

 

 6.从hashmap的put方法的具体逻辑来看，里面充斥着线程不安全因素：

1）map为空时，同时初始化map

2）hash冲突时，同时操作链表

3）同时rehash时造成机器load高

 

 7.元素为什么放在链表的头部：因为单链表，放头部最快

 

 8.LinkedHashMap的实现：继承于HashMap，内部的Entry也继承于HashMap.Entry，增加了属性before,after，另外，重写了get,addEntry,createEntry方法，提供了iterator相关方法。

 

 9.TreeMap的实现，重点看put方法

Java代码  
  1. public V put(K key, V value) {  
  2.         Entry<K,V> t = root;  
  3.         if (t == null) {  
  4.             compare(key, key); // type (and possibly null) check  
  5.   
  6.             root = new Entry<>(key, value, null);  
  7.             size = 1;  
  8.             modCount++;  
  9.             return null;  
  10.         }  
  11.         int cmp;  
  12.         Entry<K,V> parent;  
  13.         // split comparator and comparable paths  
  14.         Comparator<? super K> cpr = comparator;  
  15.         if (cpr != null) {  
  16.             do {  
  17.                 parent = t;  
  18.                 cmp = cpr.compare(key, t.key);  
  19.                 if (cmp < 0)  
  20.                     t = t.left;  
  21.                 else if (cmp > 0)  
  22.                     t = t.right;  
  23.                 else  
  24.                     return t.setValue(value);  
  25.             } while (t != null);  
  26.         }  
  27.         else {  
  28.             if (key == null)  
  29.                 throw new NullPointerException();  
  30.             Comparable<? super K> k = (Comparable<? super K>) key;  
  31.             do {  
  32.                 parent = t;  
  33.                 cmp = k.compareTo(t.key);  
  34.                 if (cmp < 0)  
  35.                     t = t.left;  
  36.                 else if (cmp > 0)  
  37.                     t = t.right;  
  38.                 else  
  39.                     return t.setValue(value);  
  40.             } while (t != null);  
  41.         }  
  42.         Entry<K,V> e = new Entry<>(key, value, parent);  
  43.         if (cmp < 0)  
  44.             parent.left = e;  
  45.         else  
  46.             parent.right = e;  
  47.         fixAfterInsertion(e);  
  48.         size++;  
  49.         modCount++;  
  50.         return null;  
  51.     }  

 

  10. jdk7 ConcurrentHashMap的get,size,put方法

Java代码  
  1. public V get(Object key) {  
  2.         Segment<K,V> s; // manually integrate access methods to reduce overhead  
  3.         HashEntry<K,V>[] tab;  
  4.         int h = hash(key);  
  5.         long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;  
  6.         if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&  
  7.             (tab = s.table) != null) {  
  8.             for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile  
  9.                      (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);  
  10.                  e != null; e = e.next) {  
  11.                 K k;  
  12.                 if ((k = e.key) == key || (e.hash == h && key.equals(k)))  
  13.                     return e.value;  
  14.             }  
  15.         }  
  16.         return null;  
  17.     }  

 

Java代码  
  1. public int size() {  
  2.         // Try a few times to get accurate count. On failure due to  
  3.         // continuous async changes in table, resort to locking.  
  4.         final Segment<K,V>[] segments = this.segments;  
  5.         int size;  
  6.         boolean overflow; // true if size overflows 32 bits  
  7.         long sum;         // sum of modCounts  
  8.         long last = 0L;   // previous sum  
  9.         int retries = -1; // first iteration isn't retry  
  10.         try {  
  11.             for (;;) {  
  12.                 if (retries++ == RETRIES_BEFORE_LOCK) {  
  13.                     for (int j = 0; j < segments.length; ++j)  
  14.                         ensureSegment(j).lock(); // force creation  
  15.                 }  
  16.                 sum = 0L;  
  17.                 size = 0;  
  18.                 overflow = false;  
  19.                 for (int j = 0; j < segments.length; ++j) {  
  20.                     Segment<K,V> seg = segmentAt(segments, j);  
  21.                     if (seg != null) {  
  22.                         sum += seg.modCount;  
  23.                         int c = seg.count;  
  24.                         if (c < 0 || (size += c) < 0)  
  25.                             overflow = true;  
  26.                     }  
  27.                 }  
  28.                 if (sum == last)  
  29.                     break;  
  30.                 last = sum;  
  31.             }  
  32.         } finally {  
  33.             if (retries > RETRIES_BEFORE_LOCK) {  
  34.                 for (int j = 0; j < segments.length; ++j)  
  35.                     segmentAt(segments, j).unlock();  
  36.             }  
  37.         }  
  38.         return overflow ? Integer.MAX_VALUE : size;  
  39.     }  

  

Java代码  
  1. public V put(K key, V value) {  
  2.         Segment<K,V> s;  
  3.         if (value == null)  
  4.             throw new NullPointerException();  
  5.         int hash = hash(key);  
  6.         int j = (hash >>> segmentShift) & segmentMask;  
  7.         if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck  
  8.              (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment  
  9.             s = ensureSegment(j);  
  10.         return s.put(key, hash, value, false);  
  11.     }  
  12.   
  13. public V putIfAbsent(K key, V value) {  
  14.         Segment<K,V> s;  
  15.         if (value == null)  
  16.             throw new NullPointerException();  
  17.         int hash = hash(key);  
  18.         int j = (hash >>> segmentShift) & segmentMask;  
  19.         if ((s = (Segment<K,V>)UNSAFE.getObject  
  20.              (segments, (j << SSHIFT) + SBASE)) == null)  
  21.             s = ensureSegment(j);  
  22.         return s.put(key, hash, value, true);  
  23.     }  
  24.   
  25. final V put(K key, int hash, V value, boolean onlyIfAbsent) {  
  26.             HashEntry<K,V> node = tryLock() ? null :  
  27.                 scanAndLockForPut(key, hash, value);  
  28.             V oldValue;  
  29.             try {  
  30.                 HashEntry<K,V>[] tab = table;  
  31.                 int index = (tab.length - 1) & hash;  
  32.                 HashEntry<K,V> first = entryAt(tab, index);  
  33.                 for (HashEntry<K,V> e = first;;) {  
  34.                     if (e != null) {  
  35.                         K k;  
  36.                         if ((k = e.key) == key ||  
  37.                             (e.hash == hash && key.equals(k))) {  
  38.                             oldValue = e.value;  
  39.                             if (!onlyIfAbsent) {  
  40.                                 e.value = value;  
  41.                                 ++modCount;  
  42.                             }  
  43.                             break;  
  44.                         }  
  45.                         e = e.next;  
  46.                     }  
  47.                     else {  
  48.                         if (node != null)  
  49.                             node.setNext(first);  
  50.                         else  
  51.                             node = new HashEntry<K,V>(hash, key, value, first);  
  52.                         int c = count + 1;  
  53.                         if (c > threshold && tab.length < MAXIMUM_CAPACITY)  
  54.                             rehash(node);  
  55.                         else  
  56.                             setEntryAt(tab, index, node);  
  57.                         ++modCount;  
  58.                         count = c;  
  59.                         oldValue = null;  
  60.                         break;  
  61.                     }  
  62.                 }  
  63.             } finally {  
  64.                 unlock();  
  65.             }  
  66.             return oldValue;  
  67.         }  
  68.   
  69. /** 
  70.          * Scans for a node containing given key while trying to 
  71.          * acquire lock, creating and returning one if not found. Upon 
  72.          * return, guarantees that lock is held. UNlike in most 
  73.          * methods, calls to method equals are not screened: Since 
  74.          * traversal speed doesn't matter, we might as well help warm 
  75.          * up the associated code and accesses as well. 
  76.          * 
  77.          * @return a new node if key not found, else null 
  78.          */  
  79.         private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {  
  80.             HashEntry<K,V> first = entryForHash(this, hash);  
  81.             HashEntry<K,V> e = first;  
  82.             HashEntry<K,V> node = null;  
  83.             int retries = -1; // negative while locating node  
  84.             while (!tryLock()) {  
  85.                 HashEntry<K,V> f; // to recheck first below  
  86.                 if (retries < 0) {  
  87.                     if (e == null) {  
  88.                         if (node == null) // speculatively create node  
  89.                             node = new HashEntry<K,V>(hash, key, value, null);  
  90.                         retries = 0;  
  91.                     }  
  92.                     else if (key.equals(e.key))  
  93.                         retries = 0;  
  94.                     else  
  95.                         e = e.next;  
  96.                 }  
  97.                 else if (++retries > MAX_SCAN_RETRIES) {  
  98.                     lock();  
  99.                     break;  
  100.                 }  
  101.                 else if ((retries & 1) == 0 &&  
  102.                          (f = entryForHash(this, hash)) != first) {  
  103.                     e = first = f; // re-traverse if entry changed  
  104.                     retries = -1;  
  105.                 }  
  106.             }  
  107.             return node;  
  108.         }  
原文链接:[http://wely.iteye.com/blog/2334552]

转载地址：http://zhyax.baihongyu.com/

你可能感兴趣的文章
关于在VS2005中编写DLL遇到 C4251 警告的解决办法
查看>>
FT Partners CEO：Fintech游戏才刚刚开始，未来真正的关注点在这里
查看>>
Go语言大神亲述:历七劫方可成为程序员!
查看>>
【盘点】2017杭州云栖大会迁云实战Workshop
查看>>
Visual Studio 2008提高工作效率的小技巧
查看>>
深入研究Clang（七） Clang Lexer代码阅读笔记之Lexer
查看>>
对话依图医疗总裁倪浩：AI 产品只是第一步，未来要和医院制定中国儿童骨龄新标准...
查看>>
mysql并行复制
查看>>
Duilib学习笔记《06》— 窗体基类WindowImpBase
查看>>
共筑开放AI生态：ONNX标准得到华为、英特尔等更多厂商支持
查看>>
辅助企业IT进化的路上 数人云的不变与多变
查看>>
释放大数据生产力 Kyligence发布最新版旗舰产品KAP2.4
查看>>
惠普：应把大数据科学家作为一种共享资源
查看>>
中国人工智能学会通讯——自然语言处理中的技术评测
查看>>
开启openssl
查看>>
你必须关注超融合基础设施的理由
查看>>
善用佳软站长：畅谈大数据时代的知识管理
查看>>
AT&T：BYOD在2015年达“拐点”
查看>>
一款高端精密的DDoS定制工具包
查看>>
甲骨文5000万美元收购以色列大数据公司Crosswise
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-12-28 23:36:01   当前IP: 3.12.155.47   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我