手写Java HashMap核心源码
上一章手写LinkedList核心源码，本章我们来手写Java HashMap的核心源码。 我们来先了解一下HashMap的原理。HashMap 字面意思 hash + map，map是映射的意思，HashMap就是用hash进行映射的意思。不明白？没关系。我们来具体讲解一下HashMap的原理。
HashMap 使用分析
1//1 存 2HashMap<String,String> map = new HashMap<>(); 3map.put("name","tom"); 4 5//2 取 6System.out.println(map.get("name"));//输出 tom
使用就是这么简单。
HashMap 原理分析
我们知道，Object类有一个hashCode()方法，返回对象的hashCode值，可以理解为返回了对象的内存地址，暂且不管返回的是内存地址或者其它什么也好，先不管，至于hashCode()方法回返的数是怎么算的？我们也不管
第1 我们只需要记住：这个函数返回的是一个数就行了。 第2 HashMap内部是用了一个数组来存放数据
1 HashMap是如何把 name,tom存放的？ 下面我们用一张图来演示
从上图可以看出： 注：上图中数组的大小是7，是多少都行，只是我们这里就画了7个元素，我们就以数组大小为7来说明HashMap的原理。
- 数组的大小是7，那么数组的索引范围是[0 , 6]
- 取得key也就是"name"的hashCode，这是一个数，不管这个数是多少，对7进行取余数，那么范围肯定是 [0 , 6]，正好和数组的索引是一样的。
- "name".hashCode() % 7 的值假如为2 ，那么value也就是"tom"应该存放的位置就是2
- data[2] = "tom" ,存到数组中。是不是很巧妙。
2 下面再来看看如何取？ 也用一张图来演示底层原理，如下
由上图可知:
- 首先也是获取key也就是"name"的hashCode值
- 用hashCode值对数组的大小 7 进行取余数，和存的时候运行一样，肯定也是2
- 从数组的第 2 个位置把value取出，即: String value = data[2]
注：有几点需要注意
- 某个对象的hashCode()方法返回的值，在任何时候调用，返回的值都是一样的
- 对一个数 n 取余数 ,范围是 [ 0, n - 1 ]
注：有几个问题需要解决
-
存的时候，如果不同的key的hashCode对数组取余数，都正好相同了，也就是都映射在了数组的同一位置，怎么办？这就是hash冲突问题 比如
9 % 7 == 2 ， 16 % 7 == 2都等于2 答：数组中存放的是一个节点的数据结构，节点有next属性，如果hash冲突了，单链表进行存放，取的时候也是一样，遍历链表 -
如果数组已经存满了怎么办？ 答：和ArrayList一样，进行扩容，重新映射
-
直接使用hashCode()值进行映射，产生hash冲突的概论很大，怎么办？ 答：参考JDK中HashMap中的实现，有一个hash()函数，再对hashCode()的值进行运行一下，再进行映射
由上可知：HashMap是用一个数组来存放数据，如果遇到映射的位置上面已经有值了，那么就用链表存放在当前的前面。数组+链表结构，是HashMap的底层结构 假如我们的数组里面存放的元素是QEntry，如下图：
手写 HashMap 核心源码
上面分析了原理，接下来我们用最少的代码来提示HashMap的原理。 我们就叫QHashMap类，同时数组里面的元素需要也需要定义一个类，我们定义在QHashMap类的内部。就叫QEntry
QEntry的定义如下：
1 //底层数组中存放的元素类 2 public static class QEntry<K, V> { 3 K key; //存放key 4 V value; //存放value 5 int hash; //key对应的hash值 6 7 //hash冲突时，也就是映射的位置上已经有一个元素了 8 //那么新加的元素作为链表头，已经存放的放在后面 9 //即保存在next中，一句话：添加新元素时，添加在表头 10 QEntry<K, V> next; 11 12 public QEntry(K key, V value, int hash, QEntry<K, V> next) { 13 this.key = key; 14 this.value = value; 15 this.hash = hash; 16 this.next = next; 17 } 18 }
QEntry类的定义有了，下面看下QHashMap类中需要哪些属性？ QHashMap类的定义如下图：
1public class QHashMap<K, V> { 2 //默认的数组的大小 3 private static final int DEFAULT_INITIAL_CAPACITY = 16; 4 5 //默认的扩容因子，当数据中元素的个数越多时，hash冲突也容易发生 6 //所以，需要在数组还没有用完的情况下就开始扩容 7 //这个 0.75 就是元素的个数达到了数组大小的75%的时候就开始扩容 8 //比如数组的大小是100，当里面的元素增加到75的时候，就开始扩容 9 private static final float DEFAULT_LOAD_FACTOR = 0.75f; 10 11 //存放元素的数组 12 private QEntry[] table; 13 14 //数组中元素的个数 15 private int size; 16 17 ...... 18}
只需要两个常量和两个变量就够了。 下面我们看下QHashMap的构造函数，为了简单，只实现一个默认的构造函数
1 public QHashMap() { 2 //创建一个数组，默认大小为16 3 table = new QEntry[DEFAULT_INITIAL_CAPACITY]; 4 5 //此时元素个数是0 6 size = 0; 7 }
我们来看下QHashMap是如何存放数据的 map.put("name","tom")
put()函数的实现如下：
1 /** 2 * 1 参数key,value很容易理解 3 * 2 返回V，我们知道，HashMap有一个特点， 4 * 如果调用了多次 map.put("name","tom"); map.put("name","lilei"); 5 * 后面的值会把前面的覆盖，如果出现这种情况，返回旧值，在这里返回"tom" 6 */ 7 public V put(K key, V value) { 8 //1 为了简单，key不支持null 9 if (key == null) { 10 throw new RuntimeException("key is null"); 11 } 12 13 //不直接用key.hashCode()，我们对key.hashCode()再作一次运算作为hash值 14 //这个hash()的方法我是直接从HashMap源码拷贝过来的。可以不用关心hash()算法本身 15 //只需要知道hash()输入一个数，返回一个数就行了。 16 int hash = hash(key.hashCode()); 17 18 //用key的hash值和数组的大小，作一次映射，得到应该存放的位置 19 int index = indexFor(hash, table.length); 20 21 //看看数组中，有没有已存在的元素的key和参数中的key是相等的 22 //相等则把老的值替换成新的，然后返回旧值 23 QEntry<K, V> e = table[index]; 24 while (e != null) { 25 //先比较hash是否相等，再比较对象是否相等，或者比较equals方法 26 //如果相等了，说明有一样的key,这时要更新旧值为新的value,同时返回旧的值 27 if (e.hash == hash && (key == e.key || key.equals(e.key))) { 28 V oldValue = e.value; 29 e.value = value; 30 return oldValue; 31 } 32 e = e.next; 33 } 34 35 //如果数组中没有元素的key与传的key相等的话 36 //把当前位置的元素保存下来 37 QEntry<K, V> next = table[index]; 38 39 //next有可能为null，也有可能不为null，不管是否为null 40 //next都要作为新元素的下一个节点(next传给了QEntry的构造函数) 41 //然后新的元素保存在了index这个位置 42 table[index] = new QEntry<>(key, value, hash, next); 43 44 //如果需要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，经验) 45 if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) { 46 resize(); 47 } 48 49 return null; 50 }
注释很详细，这里有几个函数 hash()函数是直接从HashMap源码中拷贝的，不用纠结这个算法。 indexFor()，传入hash和数组的大小，从而知道我们应该去哪个位置查找或保存 这两个函数的源码如下：
1 //对hashCode进行运算，JDK中HashMap的实现，直接拷贝过来了 2 static int hash(int h) { 3 h ^= (h >>> 20) ^ (h >>> 12); 4 return h ^ (h >>> 7) ^ (h >>> 4); 5 } 6 7 //根据 h 求key落在数组的哪个位置 8 static int indexFor(int h, int length) { 9 //或者 return h & (length-1) 性能更好 10 //这里我们用最容易理解的方式，对length取余数，范围就是[0,length - 1] 11 //正好是table数组的所有的索引的范围 12 13 h = h > 0 ? h : -h; //防止负数 14 15 return h % length; 16 }
还有一个扩容函数。当元素的个数大于 table.length * 0.75时，我们就开始扩容 resize()的源码如下 ：
1 //扩容，元素的个数大于 table.length * 0.75 2 //数组扩容到原来大小的2倍 3 private void resize() { 4 //新建一个数组，大小为原来数组大小的2倍 5 int newCapacity = table.length * 2; 6 QEntry[] newTable = new QEntry[newCapacity]; 7 8 QEntry[] src = table; 9 10 //遍历旧数组，重新映射到新的数组中 11 for (int j = 0; j < src.length; j++) { 12 //获取旧数组元素 13 QEntry<K, V> e = src[j]; 14 15 //释放旧数组 16 src[j] = null; 17 18 //因为e是一个链表，有可能有多个节点，循环遍历进行映射 19 while (e != null) { 20 //把e的下一个节点保存下来 21 QEntry<K, V> next = e.next; 22 23 //e这个当前节点进行在新的数组中映射 24 int i = indexFor(e.hash, newCapacity); 25 26 //newTable[i] 位置上有可能是null，也有可能不为null 27 //不管是否为null，都作为e这个节点的下一个节点 28 e.next = newTable[i]; 29 30 //把e保存在新数组的 i 的位置 31 newTable[i] = e; 32 33 //继续e的下一个节点的同样的处理 34 e = next; 35 } 36 } 37 38 //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table 39 table = newTable; 40 }
相比put()函数来说，get()就简单多了。 只需要通过hash值找到相应的数组的位置，再遍历链表，找到一个元素里面的key与传的key相等就行了。 put()方法的源码如下：
1 //根据key获取value 2 public V get(K key) { 3 4 //同样为了简单，key不支持null 5 if (key == null) { 6 throw new RuntimeException("key is null"); 7 } 8 9 //对key进行求hash值 10 int hash = hash(key.hashCode()); 11 12 //用hash值进行映射，得到应该去数组的哪个位置上取数据 13 int index = indexFor(hash, table.length); 14 15 //把index位置的元素保存下来进行遍历 16 //因为e是一个链表，我们要对链表进行遍历 17 //找到和key相等的那个QEntry，并返回value 18 QEntry<K, V> e = table[index]; 19 while (e != null) { 20 21 //比较 hash值是否相等 22 if (hash == e.hash && (key == e.key || key.equals(e.key))) { 23 return e.value; 24 } 25 26 //如果不相等，继续找下一个 27 e = e.next; 28 } 29 30 return null; 31 }
上面就是QHashMap的核心源码，我们没有实现删除。 下面是把QHashMap整个类的源码发出来
QHashMap完整源码如下：
1public class QHashMap<K, V> { 2 //默认的数组的大小 3 private static final int DEFAULT_INITIAL_CAPACITY = 16; 4 5 //默认的扩容因子，当数组的大小大于或者等于当前容量 * 0.75的时候，就开始扩容 6 private static final float DEFAULT_LOAD_FACTOR = 0.75f; 7 8 //底层用一个数组来存放数据 9 private QEntry[] table; 10 11 //数组大小 12 private int size; 13 14 //一个点节，数组中存放的单位 15 public static class QEntry<K, V> { 16 K key; 17 V value; 18 int hash; 19 QEntry<K, V> next; 20 21 public QEntry(K key, V value, int hash, QEntry<K, V> next) { 22 this.key = key; 23 this.value = value; 24 this.hash = hash; 25 this.next = next; 26 } 27 } 28 29 public QHashMap() { 30 table = new QEntry[DEFAULT_INITIAL_CAPACITY]; 31 size = 0; 32 } 33 34 //根据key获取value 35 public V get(K key) { 36 37 //同样为了简单，key不支持null 38 if (key == null) { 39 throw new RuntimeException("key is null"); 40 } 41 42 //对key进行求hash值 43 int hash = hash(key.hashCode()); 44 45 //用hash值进行映射，得到应该去数组的哪个位置上取数据 46 int index = indexFor(hash, table.length); 47 48 //把index位置的元素保存下来进行遍历 49 //因为e是一个链表，我们要对链表进行遍历 50 //找到和key相等的那个QEntry，并返回value 51 QEntry<K, V> e = table[index]; 52 while (e != null) { 53 54 //比较 hash值是否相等 55 if (hash == e.hash && (key == e.key || key.equals(e.key))) { 56 return e.value; 57 } 58 59 //如果不相等，继续找下一个 60 e = e.next; 61 } 62 63 return null; 64 } 65 66 /** 67 * 1 参数key,value很容易理解 68 * 2 返回V，我们知道，HashMap有一个特点， 69 * 如果调用了多次 map.put("name","tom"); map.put("name","lilei"); 70 * 后面的值会把前面的覆盖，如果出现这种情况，返回旧值，在这里返回"tom" 71 */ 72 public V put(K key, V value) { 73 //1 为了简单，key不支持null 74 if (key == null) { 75 throw new RuntimeException("key is null"); 76 } 77 78 //不直接用key.hashCode()，我们对key.hashCode()再作一次运算作为hash值 79 //这个hash()的方法我是直接从HashMap源码拷贝过来的。可以不用关心hash()算法本身 80 //只需要知道hash()输入一个数，返回一个数就行了。 81 int hash = hash(key.hashCode()); 82 83 //用key的hash值和数组的大小，作一次映射，得到应该存放的位置 84 int index = indexFor(hash, table.length); 85 86 //看看数组中，有没有已存在的元素的key和参数中的key是相等的 87 //相等则把老的值替换成新的，然后返回旧值 88 QEntry<K, V> e = table[index]; 89 while (e != null) { 90 //先比较hash是否相等，再比较对象是否相等，或者比较equals方法 91 //如果相等了，说明有一样的key,这时要更新旧值为新的value,同时返回旧的值 92 if (e.hash == hash && (key == e.key || key.equals(e.key))) { 93 V oldValue = e.value; 94 e.value = value; 95 return oldValue; 96 } 97 e = e.next; 98 } 99 100 //如果数组中没有元素的key与传的key相等的话 101 //把当前位置的元素保存下来 102 QEntry<K, V> next = table[index]; 103 104 //next有可能为null，也有可能不为null，不管是否为null 105 //next都要作为新元素的下一个节点(next传给了QEntry的构造函数) 106 //然后新的元素保存在了index这个位置 107 table[index] = new QEntry<>(key, value, hash, next); 108 109 //如果需要扩容，元素的个数大于 table.length * 0.75 (别问为什么是0.75，经验) 110 if (size++ >= (table.length * DEFAULT_LOAD_FACTOR)) { 111 resize(); 112 } 113 114 return null; 115 } 116 117 //扩容，元素的个数大于 table.length * 0.75 118 //数组扩容到原来大小的2倍 119 private void resize() { 120 //新建一个数组，大小为原来数组大小的2倍 121 int newCapacity = table.length * 2; 122 QEntry[] newTable = new QEntry[newCapacity]; 123 124 QEntry[] src = table; 125 126 //遍历旧数组，重新映射到新的数组中 127 for (int j = 0; j < src.length; j++) { 128 //获取旧数组元素 129 QEntry<K, V> e = src[j]; 130 131 //释放旧数组 132 src[j] = null; 133 134 //因为e是一个链表，有可能有多个节点，循环遍历进行映射 135 while (e != null) { 136 //把e的下一个节点保存下来 137 QEntry<K, V> next = e.next; 138 139 //e这个当前节点进行在新的数组中映射 140 int i = indexFor(e.hash, newCapacity); 141 142 //newTable[i] 位置上有可能是null，也有可能不为null 143 //不管是否为null，都作为e这个节点的下一个节点 144 e.next = newTable[i]; 145 146 //把e保存在新数组的 i 的位置 147 newTable[i] = e; 148 149 //继续e的下一个节点的同样的处理 150 e = next; 151 } 152 } 153 154 //所有的节点都映射到了新数组上，别忘了把新数组的赋值给table 155 table = newTable; 156 } 157 158 //对hashCode进行运算，JDK中HashMap的实现，直接拷贝过来了 159 static int hash(int h) { 160 h ^= (h >>> 20) ^ (h >>> 12); 161 return h ^ (h >>> 7) ^ (h >>> 4); 162 } 163 164 //根据 h 求key落在数组的哪个位置 165 static int indexFor(int h, int length) { 166 //或者 return h & (length-1) 性能更好 167 //这里我们用最容易理解的方式，对length取余数，范围就是[0,length - 1] 168 //正好是table数组的所有的索引的范围 169 170 h = h > 0 ? h : -h; //防止负数 171 172 return h % length; 173 } 174 175}
上面就是QHashMap的原理。下面我们写一段测试代码来看下我们的QHashMap能不能正常运行。测试代码如下：
1 public static void main(String[] args) { 2 QHashMap<String, String> map = new QHashMap<>(); 3 map.put("name", "tom"); 4 map.put("age", "23"); 5 map.put("address", "beijing"); 6 String oldValue = map.put("address", "shanghai"); //key一样，返回旧值，保存新值 7 8 System.out.println(map.get("name")); 9 System.out.println(map.get("age")); 10 11 System.out.println("旧值=" + oldValue); 12 System.out.println("新值=" + map.get("address")); 13 }
输出如下：
1tom 223 3旧值=beijing 4新值=shanghai
通过上面的简单的实现了QHashMap,还有好多功能没有实现，比较remove,clear,containsKey()等，还有遍历相关，有兴趣的读者可以自己实现