开发文章

深入学习HashMap

1、HashMap 是什么
   HashMap是散列表,K-V键值对集合。

2、HashMap 数据结构
1) 容量,增长因子,增长阔值, hashSeed 哈希因子,在
    private int threshold; // =容量 * loadFactor 增长因子 默认= 16 * 0.75 = 12 ,容量的增长,主要原因是尽量避免Hash冲突,就是为了将 Map.Entry线性分布在 Map.Entry[] talbe中,也就是尽量做到 table数组中的元素的 next 为 null;
    private loat loadFactor;//增长因子,默认为0.75 ,
    transient int hashSeed = 0;  // initHashSeedAsNeeded  初始化,并用于 final int hash(Object k) 方法中,算key的哈希值
   
2)private transient Map.Entry[]  table;  也就是HashMap,内部维护着一个 元素类型为Map.Entry的数组。但这个数组是非连续存放的比如,第1个位置,第4个位置有值,
                                                  第2个位置,第三个位置为 null。

3)Map.Entry<K,V> 结构详解
      private int hash;
      private K key;
      private V value;
      prinvate Map.Entry<K,V> next;    // 这里是关键中的关键

HashMap 存放图解

HashMap 存放图解.png

 

复制内容到剪贴板
  1. 3.1 put(K key, V value);    
  2. /**  
  3.      * Associates the specified value with the specified key in this map.  
  4.      * If the map previously contained a mapping for the key, the old  
  5.      * value is replaced.  
  6.      *  
  7.      * @param key key with which the specified value is to be associated  
  8.      * @param value value to be associated with the specified key  
  9.      * @return the previous value associated with <tt>key</tt>, or  
  10.      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.  
  11.      *         (A <tt>null</tt> return can also indicate that the map  
  12.      *         previously associated <tt>null</tt> with <tt>key</tt>.)  
  13.      */    
  14.     public V put(K key, V value) {    
  15.         if (table == EMPTY_TABLE) {    
  16.             inflateTable(threshold);    
  17.         }    
  18.         if (key == null)    
  19.             return putForNullKey(value);    
  20.         int hash = hash(key);    
  21.         int i = indexFor(hash, table.length);    
  22.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {    
  23.             Object k;    
  24.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {    
  25.                 V oldValue = e.value;    
  26.                 e.value = value;    
  27.                 e.recordAccess(this);    
  28.                 return oldValue;    
  29.             }    
  30.         }    
  31.     
  32.         modCount++;    
  33.         addEntry(hash, key, value, i);    
  34.         return null;    
  35.     }    
  36.     
  37.     实现思路:    
  38.    首先,table == EMPTY_TABLE,判断是否是空数组,如果是,开始初始化HashMap的 table数据结构,inflate 膨胀,扩容的意思。那我们把目光投入到 inflateTable方法中    
  39.     /**  
  40.      * Inflates the table.  
  41.      */    
  42.     private void inflateTable(int toSize) {        
  43.         // Find a power of 2 >= toSize    
  44.         int capacity = roundUpToPowerOf2(toSize);    // 首先计算容量, toSize 容量为 threshold,在构造方法中,threshold默认等于初始容量,也就是16    
  45.     
  46.         threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // 然后重新算成 threshold的值,默认为 capacity * loadFactor//初始化数组 容量为 capacity    
  47.         initHashSeedAsNeeded(capacity);    
  48.     }    
  49.     
  50.     private static int roundUpToPowerOf2(int number) {    
  51.         // assert number >= 0 : "number must be non-negative";    
  52.         return number >= MAXIMUM_CAPACITY    
  53.                 ? MAXIMUM_CAPACITY    
  54.                 : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;    
  55.      }    
  56. //对于roundUpToPowerOf2解读    
  57. //   int number = 16;    
  58. //   首先与MAXIMUM_CAPACITYB比较,,基本上不会大于,故,主要看     (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;    
  59. //   Integer.highestOneBit((number - 1) << 1)     
  60. // (16 - 1) << 1   15的二进制为    00000000 00000000 00000000   00001111;然后向左移动一位,变为00000000 00000000 00000000 00011110    
  61. // Integer.highestOneBit 函数,就是保留高位的第一个1,其他全部为0,所以,00000000 00000000 00000000 00010000,等于16    
  62. //所以在初始化是,,int capacity = roundUpToPowerOf2(threshold),也就是能确保 HashMap的容量保持在2的幂。    
  63. //然后计算threshold,增长阔值,也就是当容量达到该值后,需要重新扩充容量。    
  64.     
  65. /**  
  66.      * Initialize the hashing mask value. We defer initialization until we  
  67.      * really need it.  
  68.      */    
  69.     final boolean initHashSeedAsNeeded(int capacity) {    
  70.         boolean currentAltHashing = hashSeed != 0;    
  71.         boolean useAltHashing = sun.misc.VM.isBooted() &&    
  72.                 (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);    
  73.         boolean switching = currentAltHashing ^ useAltHashing;    
  74.         if (switching) {    
  75.             hashSeed = useAltHashing    
  76.                 ? sun.misc.Hashing.randomHashSeed(this)    
  77.                 : 0;    
  78.         }    
  79.         return switching;    
  80.     }    
  81.     
  82.     
  83. 继续上面的代码,执行完  inflate 容量初始化后,    
  84.     public V put(K key, V value) {    
  85.         if (table == EMPTY_TABLE) {    
  86.             inflateTable(threshold);                      //初始化HashMap数据接口,主要包括 Map.Entry[] table,  int threshold, hasSeed;    
  87.         }    
  88.         if (key == null)                                       // HashTable 支持key 为null    
  89.             return putForNullKey(value);    
  90.         int hash = hash(key);                              //计算 key 的hash值                
  91.         int i = indexFor(hash, table.length);       // 根据hash值,和表当前的长度,得到一个在数组中的 下标。;重点关注一下  indexFor 方法的实现。    
  92.                                                                        // 该算法主要返回一个索引,0 - table.length-1的数组下标。    
  93.     
  94.         for (Entry<K,V> e = table[i]; e != null; e = e.next) {   //接下来,找到  table[i]处,以及该处的数据链,看是否存在相同的key;判断key想到,首先判断hash值                                                                                            //是否相等,然后再 判断key的equals方法是否相等    
  95.             Object k;    
  96.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {    
  97.                 V oldValue = e.value;    
  98.                 e.value = value;    
  99.                 e.recordAccess(this);    
  100.                 return oldValue;    
  101.             }    
  102.         }    
  103.     
  104.         modCount++;    
  105.         addEntry(hash, key, value, i);   // 添加元素到 HashMap,,然后将目光投入到 addEntry方法。    
  106.         return null;    
  107.     }    
  108.     
  109. /**  
  110.      * Returns index for hash code h.  
  111.      */    
  112.     static int indexFor(int h, int length) {       
  113.         // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";    
  114.         return h & (length-1);    
  115.     }    
  116.     
  117.     
  118. 接下来,重点关注 HashMap 增加一个Entry的实现过程。    
  119. /**  
  120.      * Adds a new entry with the specified key, value and hash code to  
  121.      * the specified bucket.  It is the responsibility of this  
  122.      * method to resize the table if appropriate.  
  123.      *  
  124.      * Subclass overrides this to alter the behavior of put method.  
  125.      */    
  126.     void addEntry(int hash, K key, V value, int bucketIndex) {    
  127.         if ((size >= threshold) && (null != table[bucketIndex])) {   // 是否需要扩容的判断;JDK1.7以后的扩容条件;size大于等于threshold,并且新添加元素所在                                                                                                        // 的索引值不等为空,也就是当size达到或超过threshold,新增加元素,只要不会引起hash冲                                                                                                            //突,则不扩容;JDK1.7之前,只要超过threshold,就扩容。如果需要扩容,长度增长到原来的两                                                                                                      //倍。接下来关注一下 resize方法的实现    
  128.             resize(2 * table.length);    
  129.             hash = (null != key) ? hash(key) : 0;    
  130.             bucketIndex = indexFor(hash, table.length);    
  131.         }    
  132.     
  133.         createEntry(hash, key, value, bucketIndex);    
  134.     }    

 

复制内容到剪贴板
  1. private Set<Map.Entry<K,V>> entrySet0() {    
  2.        Set<Map.Entry<K,V>> es = entrySet;    
  3.        return es != null ? es : (entrySet = new EntrySet());    
  4. }    
  5.     
  6. //所以代码的关键点在与   new EntrySet();//什么是EntrySet,原来是HashMap中的一静态的内部类,该类继承AbstractSet类,本身就是一个集合。    
  7. private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {    
  8.         public Iterator<Map.Entry<K,V>> iterator() {    
  9.             return newEntryIterator();    
  10.         }    
  11.         public boolean contains(Object o) {    
  12.             if (!(o instanceof Map.Entry))    
  13.                 return false;    
  14.             Map.Entry<K,V> e = (Map.Entry<K,V>) o;    
  15.             Entry<K,V> candidate = getEntry(e.getKey());    
  16.             return candidate != null && candidate.equals(e);    
  17.         }    
  18.         public boolean remove(Object o) {    
  19.             return removeMapping(o) != null;    
  20.         }    
  21.         public int size() {    
  22.             return size;    
  23.         }    
  24.         public void clear() {    
  25.             HashMap.this.clear();    
  26.         }    
  27.     }    
  28.     
  29. private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {    
  30.         public Map.Entry<K,V> next() {    
  31.             return nextEntry();    
  32.         }    
  33.     }    
  34.     
  35. // 重点关注一下 HashIterator 迭代器    
  36. private abstract class HashIterator<E> implements Iterator<E> {    
  37.         Entry<K,V> next;        // next entry to return     //下一个元素,因为我们知道,HashMap内部的  Map.Entry<K,V>[] table内的元素是非连续的。所以访问下一元                                                                                     // 素,不能简单的用   table[++index] 这个概念。    
  38.         int expectedModCount;   // For fast-fail 遍历时,HashMap结构变化的次数,如果在遍历期间 modCount发生变化,则直接报错,并结束遍历    
  39.         int index;                          // current slot              当前位置    
  40.         Entry<K,V> current;       // current entry   当前元素    
  41.     
  42.         HashIterator() {    
  43.             expectedModCount = modCount;                                //设置开始遍历时,记录HashMap结构调整的次数    
  44.             if (size > 0) { // advance to first entry                           // 在构造方法时,先在table数组中找到第一不为空的元素,存入next属性中。    
  45.                 Entry[] t = table;    
  46.                 while (index < t.length && (next = t[index++]) == null)    
  47.                     ;    
  48.             }    
  49.         }    
  50.     
  51.         public final boolean hasNext() {   //判断是否有下一个可迭代元素,只需要判断 next是否为空即可。    
  52.             return next != null;    
  53.         }    
  54.     
  55.         final Entry<K,V> nextEntry() {                                                // 遍历的核心算法    
  56.             if (modCount != expectedModCount)                              //如果在遍历过程,有新增元素,删除元素动作,就直接抛异常。    
  57.                 throw new ConcurrentModificationException();    
  58.             Entry<K,V> e = next;                                                        //  如果下一个元素为空,直接报元素异常     
  59.             if (e == null)    
  60.                 throw new NoSuchElementException();    
  61.                                                                                                      // nextEntry,主要实现思路是:将next的值,赋值给当前元素,然后尝试获取下一个非空Map.Entry元                                                                                                        // 素,找到后,赋值给next元素    
  62.             if ((next = e.next) == null) {                                            // 这句很关键,作用,先将 要本次返回的元素 next返回【开始遍历链表了】,如果该元素的next为空,                                                                                                     //说明该元素下面没有链表,说明该hash没有冲突,然后再遍历table数组,找到下一个非空元素。    
  63.                 Entry[] t = table;    
  64.                 while (index < t.length && (next = t[index++]) == null)    
  65.                     ;    
  66.             }    
  67.             current = e;    
  68.             return e;    
  69.         }    

 

复制内容到剪贴板
  1.         public void remove() {                                                         // 将迭代器 中current所存储的元素,对应的key,删除,然后将current域设置为空,并重新设置    
  2.                                                                                                     //  expectedModCount的值等于modCount,,而current的赋值操作,发送在 next方法中,故    
  3.                                                                                                     //  故,如过在遍历过程中,想删除当前元素,it.remove()方法要在it.next()方法之后调用。    
  4.             if (current == null)    
  5.                 throw new IllegalStateException();    
  6.             if (modCount != expectedModCount)    
  7.                 throw new ConcurrentModificationException();    
  8.             Object k = current.key;    
  9.             current = null;    
  10.             HashMap.this.removeEntryForKey(k);    
  11.             expectedModCount = modCount;    
  12.         }    
  13.     }    
  14.     
  15. //验收 再遍历 HashMap时,remove方法与next方法的使用    
  16. public static void main(String[] args) {    
  17.         // TODO Auto-generated method stub    
  18.     
  19.         HashMap<String, String> a = new HashMap();    
  20.         a.put("a""a");    
  21.         a.put("b""b");    
  22.         a.put("c""c");    
  23.         a.put("d""d");    
  24.         a.put("e""e");    
  25.         a.put("f""f");    
  26.     
  27.         int i = 0;    
  28.         for (Iterator<Map.Entry<String, String>> it = a.entrySet().iterator(); it.hasNext();) {    
  29.     
  30.             if(i == 2) {  // 如果 修改为 i == 0,,则会抛出异常 IllegalStateException 异常。    
  31.                 it.remove();    
  32.     
  33.             }    
  34.             Map.Entry<String, String> entry = it.next();    
  35.             System.out.println(entry.getKey() + ":" + entry.getValue());    
  36.             i ++;    
  37.         }    
  38.     
  39.         System.out.println(a);    
  40.     
  41.     }    
  42. -----------------------------3.2 HashMap 的遍历    public Set<Map.Entry>  entrySet(); end-----------------------    

 

感谢 唯有坚持不懈 支持 磐实编程网 原文地址:
blog.csdn.net/prestigeding/article/details/52861420

文章信息

发布时间:2016-10-19

作者:唯有坚持不懈

发布者:aquwcw

浏览次数: