hashMap原理剖析

　　在日常开发中，hashMap应该算是比较常用的一个类了，今天就来学习一下hashMap的实现原理。

　　概念

　　　　1.什么时hash？

　　　　　　书面定义：就是把一个不固定长度的二进制值映射成一个固定长度的二进制值。

　　　　　　个人理解：每一个人都有不同的属性，省份，出生日期，身高，体重等等，这其实就相当于一个不固定长度的二进制值，而身份证号码就是一个唯一的标识，根据每个人的出生信息，按照一定的规则映射成身份证号码，而这个号码就相当于一个固定的二进制值。而这个映射关系就相当于hash算法，身份证号码就相当于hash值。

　　　　2.hash算法

　　　　　　除留余数法：key%table.leng = 2 就是我们需要存放的位置的索引。

　　　　　　　　有时候会出现key1%table.leng = 3 key2%table.leng = 3 这样就会造成hash冲突。而这些冲突的位置会创建一个单向的链表去存储数据。

　　　　　　平方取中法：将一个m位数的数字区平方，得到一个2m的数字，如果不足2m则前面补0，取中间的m位数字。

　　　　3.为什么会存在这样的数据结构？

　　　　　　为了更好的存、取数据，基本上要做到时间复杂度越低越好。

　　实现

　　　　我们都知道jdk的hashMap是需要实现一个顶层接口Map的，接下来我们来自己实现一个hashMap。

　　　　在hashMap中其实是一个数组存放着entry对象，entry只能够有一个key，一个value，一个entry类型的next指针，其中key存的是hash值，value存的是存放在hashMap的对象，而next存的是hash冲突的下一个对象的引用。所以我们来创建自己的Map接口MyMap

 1 public interface MyMap<K,V> {
 2     
 3     public V put (K k, V v);
 4     
 5     public V get(K k);
 6     
 7     public int size();
 8     
 9     V remove(Object key);
10     
11     void putAll(Map<? extends K, ? extends V> m);
12     
13     void clear();
14     
15     public interface Entry<K, V>{
16         public K getKey();
17         
18         public V getValue(K k);
19         
20         V setValue(V value);
21        22     }
23 }

　　　　下面去写实现类myHashMap，实现myMap接口。

　　　　在上面定义的myMap中有一个内部的接口Entry，而实现类中有一个内部类叫Entry实现类myMap中的接口Entry，而Entry中需要定义key，value，还有一个Entry类型的next的指针，指向下一个链表数据。

 1 class Entry<K, V> implements MyMap.Entry<K, V>{
 2         
 3         final K k;
 4         
 5         V v;
 6         
 7         //next指针，指向下一个链表数据
 8         Entry<K, V> next;
 9 
10         @Override
11         public K getKey() {
12             // TODO Auto-generated method stub
13             return null;
14         }
15 
16         @Override
17         public V getValue(K k) {
18             // TODO Auto-generated method stub
19             return null;
20         }
21 
22         @Override
23         public V setValue(V value) {
24             // TODO Auto-generated method stub
25             return null;
26         }
27         
28     }

　　　　下面去实现接口中定义的方法。

　　　　　　　定义好Entry中的构造器。

1         //构造器
2         public Entry(K k, V v, Entry<K, V> next) {
3             super();
4             this.k = k;
5             this.v = v;
6             this.next = next;
7         }

　　　　　　　实现getkey，getValue，setValue。

 1         @Override
 2         public K getKey() {
 3             return k;
 4         }
 5 
 6         @Override
 7         public V getValue(K k) {
 8             return v;
 9         }
10 
11         @Override
12         public V setValue(V value) {
13             V oldvale = v;
14             v = value;
15             return oldvale;
16         }

　　　　　　Entry中的方法实现以后去实现myHashMap的方法。

　　　　　　实现前先将变量定义好，一个数组的默认长度，一个负载因子，一个存放Entry的数组，一个数组中默认存放元素的个数。

 1 　　//默认数组长度
 2     private static int dafaultlength = 16;
 3     
 4     //负载因子
 5     private static double defaultLoad = 0.75;
 6     
 7     //存放Entry对象的数组
 8     private Entry<K, V>[] table = null;
 9     
10     //数组中存储元素个数
11     private int size = 0;

　　　　　　实现put方法前先将hash算法定义好。

 1      /**
 2      * 定义hash算法，除留余数法
 3      * @return hash值
 4      */
 5     private int getIndex(K k){
 6         
 7         int m = dafaultlength; 
 8         //因为hashCode有可能是一个负数，所以结果有可能是一个负数
 9         int indext = k.hashCode() % m;
10         
11         return indext >= 0 ? indext : -indext;
12     }

　　　在我们存数据时，如果我们的数组长度一直默认为16的话势必会造成线性表上的每一个位置上都会存在hash冲突，而每一个位置的单向链表就会特别长，所以我们应该定义一个负载因子，当达到这个负载因子之后数组扩容。但是扩容就存在一个问题，我们是否要对之前老表的数据再hash呢？答案是肯定的。所以这里还需要一个再hash的方法。

 1     /**
 2      * 递归取单向链表的元素
 3      * @param entry
 4      * @param list
 5      */
 6     private void findEntryByNext (Entry<K,V> entry, List<Entry<K, V>> list){
 7         if (entry != null && entry.next == null){
 8             list.add(entry);
 9             findEntryByNext(entry.next, list);
10         } else {
11             list.add(entry);
12         }
13     }

 1     /**
 2      * 数组扩容时，再hash
 3      */
 4     private void reHash (Entry<K, V>[] newTable){
 5         List<Entry<K, V>> list = new ArrayList<Entry<K,V>>();
 6         //for循环取线性表的数据
 7         for (int i = 0; i < table.length; i++) {
 8             if (table[i] == null){
 9                 continue;
10             }
11             //递归取单向链表的元素
12             findEntryByNext(table[i], list);
13         }
14         
15         //再hash
16         if (list.size() > 0){
17             size = 0;
18             defaultlength = defaultlength * 2;
19             table = newTable;
20             
21             for (Entry<K, V> entry : list) {
22                 if (entry.next != null){
23                     entry.next = null;
24                 }
25                 put(entry.getKey(), entry.getValue());
26             }
27         }
28     }

 1     /**
 2      * 数组扩容：
 3      * 我们存数据时，如果我们的数组长度一直默认为16的话势必会造成线性表上的每一
 4      * 个位置上都会存在hash冲突，而每一个位置的单向链表就会特别长，
 5      * 所以我们应该定义一个负载因子，当达到这个负载因子之后数组扩容。　
 6      */
 7     private void up2size (){
 8         Entry<K, V>[] newTable = new Entry[2 * defaultlength];
 9         reHash(newTable);
10     }

　　　　　　　实现put方法：

　　　　　　　1.根据k得到index

　　　　　　　2.将index位置的元素拿出来

　　　　　　　3.判断该位置是否有元素存在，如果这个位置不存在元素，直接将值存入，而这里的entry为null，如果这个位置存在元素，则这个entry对象将老元素位置占用，并且next指向存在的老元素。

 1     @Override
 2     public V put(K k, V v) {
 3         //1.根据k得到index
 4         int index = getIndex(k);
 5         //2.将index位置的元素拿出来
 6         Entry<K, V> entry = table[index];
 7         //3.判断该位置是否有元素存在
 8         if (entry == null){
 9             //如果这个位置不存在元素，直接将值存入，而这里的entry为null
10             table[index] = newEntry(k, v, entry);
11             size ++;
12         } else {
13             //如果这个位置存在元素，则这个entry对象将老元素位置占用，并且next指向存在的老元素。
14             table[index] = newEntry(k, v, entry);
15         }
16         return v;
17     }

　　　　实现get方法

　　　　　　首先通过hash值获取线性表的位置，然后通过比较获取单向链表中的Enery对象

 1     /**
 2      * 递归获取单向链表中的Entry对象
 3      * @param k
 4      * @param entry
 5      * @return
 6      */
 7     private V findValueEqualKey (K k, Entry<K, V> entry){
 8         if (k == entry.getKey() || k.equals(entry.getKey())){
 9             return entry.getValue();
10         }
11         if (entry.next != null){
12             findValueEqualKey(k, entry.next);
13         }
14         return null;
15     }

1     @Override
2     public V get(K k) {
3         int index = getIndex(k);
4         if (table[index] == null){
5             return null;
6         }
7         return findValueEqualKey(k, table[index]);
8     }

　　　　实现remove方法：还是通过index查找到单向链表，然后递归找到删除元素的上一个元素，将上一个元素的next指向该元素的后一个元素。

 1     @Override
 2     public V remove(K k) {
 3         int index = getIndex(k);
 4         if (table[index] == null){
 5             return null;
 6         }
 7         if (k == table[index].getKey() || k.equals(table[index].getKey())){
 8             table[index] = table[index].next;
 9             return table[index].getValue();
10         }
11         Entry<K, V> entry = findMoveEntry(k, table[index]);
12         if (entry == null){
13             return null;
14         }
15         Entry<K, V> moveEntry = entry.next;
16         entry.next = entry.next.next;
17         return moveEntry.getValue();
18     }
19 
20     private Entry<K, V> findMoveEntry(K k, Entry<K, V> entry){
21         if (entry.next == null){
22             return null;
23         }
24         if (k == entry.next.getKey() || k.equals(entry.next.getKey())){
25             return entry;
26         }
27         findMoveEntry(k, entry.next);
28         return null;
29     }

　　　　看了上面的方法，其实对hashMap的结构有了一定的了解，在hashMap中还有一些其他方法，就不在这一一实现了。

　　　　最后附上实现类中的全部代码。

  1 package hash;
  2 
  3 import java.util.ArrayList;
  4 import java.util.List;
  5 import java.util.Map;
  6 
  7 public class MyHashMap<K, V> implements MyMap<K, V> {
  8     
  9     //默认数组长度
 10     private static int defaultlength = 16;
 11     
 12     //负载因子
 13     private static double defaultLoad = 0.75;
 14     
 15     //存放Entry对象的数组
 16     private Entry<K, V>[] table = null;
 17     
 18     //数组中存储元素个数
 19     private int size = 0;
 20     
 21     public void MyHashMap(int defaultlength, double defaultLoad){
 22         defaultlength = this.defaultlength;
 23         defaultLoad = this.defaultLoad;
 24         table = new Entry[defaultlength];
 25     }
 26     
 27     public MyHashMap (){
 28         this.MyHashMap(defaultlength, defaultLoad);
 29     }
 30 
 31     @Override
 32     public V put(K k, V v) {
 33         //数组扩容
 34         if (size > defaultlength * defaultLoad){
 35             up2size();
 36         }
 37         //1.根据k得到index
 38         int index = getIndex(k);
 39         //2.将index位置的元素拿出来
 40         Entry<K, V> entry = table[index];
 41         //3.判断该位置是否有元素存在
 42         if (entry == null){
 43             //如果这个位置不存在元素，直接将值存入，而这里的entry为null
 44             table[index] = newEntry(k, v, entry);
 45             size ++;
 46         } else {
 47             //如果这个位置存在元素，则这个entry对象将老元素位置占用，并且next指向存在的老元素。
 48             table[index] = newEntry(k, v, entry);
 49         }
 50         return v;
 51     }
 52     
 53     /**
 54      * 数组扩容：
 55      * 我们存数据时，如果我们的数组长度一直默认为16的话势必会造成线性表上的每一
 56      * 个位置上都会存在hash冲突，而每一个位置的单向链表就会特别长，
 57      * 所以我们应该定义一个负载因子，当达到这个负载因子之后数组扩容。　
 58      */
 59     private void up2size (){
 60         Entry<K, V>[] newTable = new Entry[2 * defaultlength];
 61         reHash(newTable);
 62     }
 63     
 64     /**
 65      * 数组扩容时，再hash
 66      */
 67     private void reHash (Entry<K, V>[] newTable){
 68         List<Entry<K, V>> list = new ArrayList<Entry<K,V>>();
 69         //for循环取线性表的数据
 70         for (int i = 0; i < table.length; i++) {
 71             if (table[i] == null){
 72                 continue;
 73             }
 74             //递归取单向链表的元素
 75             findEntryByNext(table[i], list);
 76         }
 77         
 78         //再hash
 79         if (list.size() > 0){
 80             size = 0;
 81             defaultlength = defaultlength * 2;
 82             table = newTable;
 83             
 84             for (Entry<K, V> entry : list) {
 85                 if (entry.next != null){
 86                     entry.next = null;
 87                 }
 88                 put(entry.getKey(), entry.getValue());
 89             }
 90         }
 91     }
 92     
 93     /**
 94      * 递归取单向链表的元素
 95      * @param entry
 96      * @param list
 97      */
 98     private void findEntryByNext (Entry<K,V> entry, List<Entry<K, V>> list){
 99         if (entry != null && entry.next == null){
100             list.add(entry);
101             findEntryByNext(entry.next, list);
102         } else {
103             list.add(entry);
104         }
105     }
106     
107     /**
108      * 获取Entry方法
109      * @param k
110      * @param v
111      * @param next
112      * @return
113      */
114     private Entry<K, V> newEntry (K k, V v, Entry<K, V> next){
115         return new Entry<K, V>(k, v, next);
116     } 
117 
118     /**
119      * 定义hash算法，除留余数法
120      * @return hash值
121      */
122     private int getIndex(K k){
123         
124         int m = defaultlength; 
125         //因为hashCode有可能是一个负数，所以结果有可能是一个负数
126         int indext = k.hashCode() % m;
127         
128         return indext >= 0 ? indext : -indext;
129     }
130     
131     @Override
132     public V get(K k) {
133         int index = getIndex(k);
134         if (table[index] == null){
135             return null;
136         }
137         return findValueEqualKey(k, table[index]);
138     }
139     
140     /**
141      * 递归获取单向链表中的Entry对象
142      * @param k
143      * @param entry
144      * @return
145      */
146     private V findValueEqualKey (K k, Entry<K, V> entry){
147         if (k == entry.getKey() || k.equals(entry.getKey())){
148             return entry.getValue();
149         }
150         if (entry.next != null){
151             findValueEqualKey(k, entry.next);
152         }
153         return null;
154     }
155 
156     @Override
157     public int size() {
158         return size;
159     }
160 
161     @Override
162     public V remove(K k) {
163         int index = getIndex(k);
164         if (table[index] == null){
165             return null;
166         }
167         if (k == table[index].getKey() || k.equals(table[index].getKey())){
168             table[index] = table[index].next;
169             return table[index].getValue();
170         }
171         Entry<K, V> entry = findMoveEntry(k, table[index]);
172         if (entry == null){
173             return null;
174         }
175         Entry<K, V> moveEntry = entry.next;
176         entry.next = entry.next.next;
177         return moveEntry.getValue();
178     }
179 
180     private Entry<K, V> findMoveEntry(K k, Entry<K, V> entry){
181         if (entry.next == null){
182             return null;
183         }
184         if (k == entry.next.getKey() || k.equals(entry.next.getKey())){
185             return entry;
186         }
187         findMoveEntry(k, entry.next);
188         return null;
189     }
190     @Override
191     public void putAll(Map<? extends K, ? extends V> m) {
192     }
193 
194     @Override
195     public void clear() {
196         Entry<K, V>[] tab = table;
197         for (int i = 0; i < tab.length; i++)
198             tab[i] = null;
199         size = 0;
200     }
201 
202     class Entry<K, V> implements MyMap.Entry<K, V>{
203         
204         final K k;
205         
206         V v;
207         
208         //next指针，指向下一个链表数据
209         Entry<K, V> next;
210         
211         //构造器
212         public Entry(K k, V v, Entry<K, V> next) {
213             super();
214             this.k = k;
215             this.v = v;
216             this.next = next;
217         }
218 
219         @Override
220         public K getKey() {
221             return k;
222         }
223 
224         @Override
225         public V getValue() {
226             return v;
227         }
228 
229         @Override
230         public V setValue(V value) {
231             V oldvale = v;
232             v = value;
233             return oldvale;
234         }
235         
236     }
237 }