hashmap 的源码分析

                                                                 Hashmap 的源码分析

            在说hashmap 之前我们要知道hashmap 是为什么产生的？

            我们平时用的数据结够离不开两个东西，一个是数组，另一个就是链表。我们知道的是在查询方面数组是的查询效率高，而且还是连续的，但是在删除或者添加元素的时候需要有大幅度的移动，比较浪费空间，链表刚好在这个增加和删除的方面效率比较高，查询方面却略有不足。

Hash表      

   是不是有一种数据结构可以吧把二者将结合起来，拥有常数数量级的查询时间和快速的插入和删除呢？答案是肯定有的，这就是我们要提起的哈希表。哈希表（(Hash table）既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。

　　      哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法—— 拉链法，我们可以理解为“链表的数组” ，如图：

 

 

　从上图我们可以发现哈希表是由数组+链表组成的，一个长度为16的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般会是有三种散列的方法让数据存储到数组中（除法散列法 ，平方散列法 ，斐波那契（Fibonacci）散列法  ），一般都是的是通过hash(key)%len获得（在java的源码中使用的是hash & (length-1))，也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中，91%16=11,155%16=11,171%16=11。所以91,155，171都存储在数组下标为12的位置。（这也可以说是一种定位的方法）

 

　　HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解，一个线性的数组怎么实现按键值对来存取数据呢？这里HashMap有做一些处理。

首先HashMap里面实现一个静态内部类Entry，其重要的属性有 key , value, next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。

 

1 /** 

2      * The table, resized as necessary. Length MUST Always be a power of two. 

3      *  FIXME 这里需要注意这句话，至于原因后面会讲到 

4      */  

5 transient Entry[] table;  

6 /**

7 *静态内部类Entry

8 *

9 */

10  static class Entry<K,V> implements Map.Entry<K,V> {

11         final K key;

12         V value;

13         Entry<K,V> next;

14         final int hash;

15 

16         /**

17          * Creates new entry.

18          */

19         Entry(int h, K k, V v, Entry<K,V> n) {

20             value = v;

21             next = n;

22             key = k;

23             hash = h;

24         }

25 

26         public final K getKey() {

27             return key;

28         }

29 

30         public final V getValue() {

31             return value;

32         }

33 

34         public final V setValue(V newValue) {

35     V oldValue = value;

36             value = newValue;

37             return oldValue;

38         }

39 

 

这些值和键队是如何在hashmap 里面调用以及存储的，下面我来详细的分析我们的hashmap内部结构。（说的有些是借鉴，但是很多都是自己。）

 

1、初始化

首先来看三个常量：
static final int DEFAULT_INITIAL_CAPACITY = 16; 

 hashmap中entry[] table初始容量：16
static final int MAXIMUM_CAPACITY = 1 << 30; 

最大容量：2的30次方 (最大不会超过2的32次方，这是内存的极致。)

static final float DEFAULT_LOAD_FACTOR = 0.75f; 
装载因子,这是在rehash 的上要用的一个重要元素。

最先开始的是构造函数，代码

 

40 public HashMap() {  

41         this.loadFactor = DEFAULT_LOAD_FACTOR;  

42         threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);  

43         table = new Entry[DEFAULT_INITIAL_CAPACITY];  

44         init();  

45     }  

Threshol和LOAD_FACTOR 的值决定着hash表是否需要rehash,table=new Entry[DEFAULT_INITIAL_CAPACITY].,默认就是开辟16个大小的空间。

另外一个构造方法：

 

 

46 public HashMap(int initialCapacity, float loadFactor) {  

47         if (initialCapacity < 0)  

48             throw new IllegalArgumentException("Illegal initial capacity: " +  

49                                                initialCapacity);  

50         if (initialCapacity > MAXIMUM_CAPACITY)  

51             initialCapacity = MAXIMUM_CAPACITY;  

52         if (loadFactor <= 0 || Float.isNaN(loadFactor))  

53             throw new IllegalArgumentException("Illegal load factor: " +  

54                                                loadFactor);  

55   

56         // Find a power of 2 >= initialCapacity  

57         int capacity = 1;  

58         while (capacity < initialCapacity)  

59             capacity <<= 1; //每次是换成2的n+1方 

60   

61         this.loadFactor = loadFactor;  

62         threshold = (int)(capacity * loadFactor);  

63         table = new Entry[capacity];  

64         init();  

65     }  

就是说传入参数的构造方法，initialCapacity 就是我们要放的数据大小，我们把重点放在：

 

 

66 while (capacity < initialCapacity)  

67            capacity <<= 1;  

上面，该代码的意思是，实际的开辟的空间要大于传入的第一个参数的值。举个例子：
new HashMap(7,0.8),loadFactor为0.8，capacity为7，通过上述代码后，capacity的值为：8.（1 << 2的结果是4,2 << 2的结果为8）。所以，最终capacity的值为8，最后通过new Entry[capacity]来创建大小为capacity的数组，所以，这种方法最红取决于capacity的大小。

但是貌似这种去8应该是最合适的，但是是不是在运行程序的时候会给我这样的数据呢？

对于这这边大家是不是还很疑惑，没事后面为大家奉上详细的介绍。
2、put(Object key,Object value)操作 
当调用put操作时，首先判断key是否为null，如下代码1处：

 

 

68 <p>public V put(K key, V value) {  

69         if (key == null)  

70             return putForNullKey(value);  

71         int hash = hash(key.hashCode());  

72         int i = indexFor(hash, table.length);  

73         for (Entry<K,V> e = table[i]; e != null; e = e.next) {  

74             Object k;  

75             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  

76                 V oldValue = e.value;  

77                 e.value = value;  

78                 e.recordAccess(this);  

79                 return oldValue;  

80             }  

81         }</p><p>        modCount++;  

82         addEntry(hash, key, value, i);  

83         return null;  

84     }</p>  

 

对于这个代码要分开来看，在key==null,时，他会return调用 putForNullKey(value)，这个函数在后面是有定义的。之后才是后面的那部分代码。
如果key是null，则调用如下代码：

 

 

85 private V putForNullKey(V value) {  

86         for (Entry<K,V> e = table[0]; e != null; e = e.next) {  

87             if (e.key == null) {  

88                 V oldValue = e.value;  

89                 e.value = value;  

90                 e.recordAccess(this);

91             //hashmap 里面的void  recordAccess(HashMap<K,V> m) {} 

92            //

93          //  这是在linkMap里的定义

94            //void recordAccess(HashMap<K,V> m) { 
            //LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; 
            //if (lm.accessOrder) { 
              //  lm.modCount++; 
                // remove(); 
               //  addBefore(lm.header); 
           // } 
        //} 

95                 return oldValue;  

96             }  

97         }  

98         modCount++;  

99         addEntry(0, null, value, 0);  

100         return null;  

101 }  

 

就是说，获取Entry的第一个元素table[0] 已经相当于一个链表，在table处存着表头，并基于第一个元素的next属性开始遍历，直到找到key为null的Entry，将其value设置为新的value值。
如果没有找到key为null的元素，则调用代码addEntry(0, null, value, 0);增加一个新的entry，代码如下：

 

 

102 void addEntry(int hash, K key, V value, int bucketIndex) {  

103     Entry<K,V> e = table[bucketIndex];  

104         table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  

105         if (size++ >= threshold)  

106             resize(2 * table.length);  

107     }  

先获取第一个元素table[bucketIndex],传给e对象，新建一个entry，key为null，value为传入的value值，next为获取的e对象。如果容量大于threshold，容量扩大2倍。

 

 

 

如果key不为null，这也是大多数的情况，重新看一下源码：

 

 

108 public V put(K key, V value) {  

109         if (key == null)  

110             return putForNullKey(value);  

111         int hash = hash(key.hashCode());//---------------2---------------  

112         int i = indexFor(hash, table.length);  

113         for (Entry<K,V> e = table[i]; e != null; e = e.next) {//--------------3-----------  

114             Object k;  

115             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  

116                 V oldValue = e.value;  

117                 e.value = value;  

118                 e.recordAccess(this);  

119                 return oldValue;  

120             }  

121         }//-------------------4------------------  

122         modCount++;//----------------5----------  

123         addEntry(hash, key, value, i);-------------6-----------  

124         return null;  

125     }  

看源码中2处，首先会找出e.hashcode()，获取key的哈希值，hashCode()是Object类的一个方法，为本地方法.hash()的源码如下：

 

126 static int hash(int h) {  

127         // This function ensures that hashCodes that differ only by  

128         // constant multiples at each bit position have a bounded  

129         // number of collisions (approximately 8 at default load factor).  

130         h ^= (h >>> 20) ^ (h >>> 12);  

131         return h ^ (h >>> 7) ^ (h >>> 4);  

132 } 

133 static int indexFor(int h, int length) {  

134        return h & (length-1);  

135    }  

 

int i = indexFor(hash, table.length);的意思，相当于int i = hash % Entry[].length;得到i后，就是在Entry数组中的位置。前面我们提到过Entry类里面有一个next属性，作用是指向下一个Entry。如， 第一个键值对A进来，通过计算其key的hash得到的i=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其i也等于0，现在怎么办？HashMap会使用和链表增加的方法一样，让最后进来的当做链表的头，然后依次右移。所以是这么做的:B.next = A,Entry[0] = B,如果又进来C,i也等于0,那么C.next = B,Entry[0] = C；这样我们发现i=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起,也就是说数组中存储的是最后插入。

 

 

  HashMap的大致实现，我们应该已经清楚。对于hash 的一些优化我想在这在介绍下。当Entr[]很大或者key很多的时候，那样是不是就看起来很麻烦了，所以在HashMap里面设置一个因素（也称为因子），随着map的size越来越大，Entry[]会以一定的规则加长长度。，这样才能保持一种均衡，这就是我们是所说rehash.，所以我再介绍一点rehash,以便解决上面的一些疑问。

1.2 hashmap的resize
       当hashmap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对hashmap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。 

         那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面annegu已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题。 

 

 

 

 

 

2、get(Object key)操作
get(Object key)操作时根据键来获取值，如果了解了put操作，get操作容易理解，先来看看源码的实现：

 

 

136 public V get(Object key) {  

137         if (key == null)  

138             return getForNullKey();  

139         int hash = hash(key.hashCode());  

140         for (Entry<K,V> e = table[indexFor(hash, table.length)];  

141              e != null;  

142              e = e.next) {  

143             Object k;  

144             if (e.hash == hash && ((k = e.key) == key || key.equals(k)))//-------------------1----------------  

145                 return e.value;  

146         }  

147         return null;  

148     }  

意思就是：1、当key为null时，调用getForNullKey()，源码如下：

 

 

149 private V getForNullKey() {  

150         for (Entry<K,V> e = table[0]; e != null; e = e.next) {  

151             if (e.key == null)  

152                 return e.value;  

153         }  

154         return null;  

155     }  

2、当key不为null时，先根据hash函数得到hash值，在更具indexFor()得到i的值，循环遍历链表，如果有：key值等于已存在的key值，则返回其value。如上述get()代码1处判断。

总结下HashMap新增put和获取get操作：

 

 

156 //存储时:  

157 int hash = key.hashCode();  

158 int i = hash % Entry[].length;  

159 Entry[i] = value;  

160   

161 //取值时:  

162 int hash = key.hashCode();  

163 int i = hash % Entry[].length;  

164 return Entry[i];  

165 

 

 

这篇主要是对hashmap做了一个比较清晰的分析，读源码分析源码，第一次做有些地方做的不好还请大家多多包涵。

 

 

<!--EndFragment-->