Java HashMap原理与实现 作者：马育民 • 2022-07-02 20:07 • 阅读：10059 # 说明 - JAVA8之前：HashMap 实现方式：数组 + 链表 - JAVA8：HashMap 实现方式：数组 + 链表 + 红黑树 ### 实现原理 1. 创建 长度是 16 的数组 2. 使用 `hash()`函数，对 `key` 算出 `hashcode` 值，并对 16 取模，算出的值，就是数组中的位置，将 元素 放入到该位置 3. 但是，**会发生冲突**，原因如下： - `hash()`函数算出 `hashcode` 值会冲突 - 由于数组长度是 16，当元素个数超过 16 时，比如会冲突 4. **解决冲突**：数组存的是链表，当冲突时，将元素放入到链表中 下图是 JAVA8的实现方式，当链表长度大于8时，转为红黑树，查询数据更快 [](/upload/0/0/1IX3bYBa3DsI.png) ### put() 方法实现过程 [](/upload/0/0/1IX3bYKYtWK3.jpg) https://zhuanlan.zhihu.com/p/21673805 # 扩容机制 当 `HashMap` 中的元素个数超过 `数组大小*loadFactor` 时，就会进行数组扩容，`loadFactor` 的默认值为 `0.75` 就是说：默认情况下，数组大小为 `16` ，那么当 `HashMap` 中元素个数超过 `16*0.75=12` 的时候，就把数组的大小扩展为 `2*16=32` ，**即扩大一倍** 然后 **重新计算每个元素在数组中的位置**，而这是一个 **非常消耗性能的操作** https://www.cnblogs.com/miaosj/p/11088613.html ### 提高性能 （不考虑 hashcode 冲突） 不发生扩容，性能就能提高，所以如果 **预知元素的个数**，那么预设元素的个数能够有效的提高性能。 比如，有 `100` 个 key/value，创建集合时指定容量： `new HashMap(100)` 但是 `new HashMap(100)` 还不是更合适的，因为 元素个数超过 `0.75*100` 时，数组就会发生扩容。 就是说为了让 `0.75 * size > 100`，`size > 100/0.75 = 134`，即创建集合时，指定 `new HashMap(134)` 才最合适 # java代码 ### Node 节点类 ``` package testmap; public class Node { private String key; private Object value; private Node next; public Node(String key, Object value) { this.key = key; this.value = value; } public String getKey() { return key; } public void setKey(String key) { this.key = key; } public Object getValue() { return value; } public void setValue(Object value) { this.value = value; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } } ``` ### MyHashTable ``` package testmap; public class MyHashTable { /** * 数组长度 */ private int ARR_LEN = 16; private Node[] table = new Node[ARR_LEN]; private int size = 0; public void put(String key,Object value){ // 根据 hashcode，算出应该在 数组中的哪个位置 int index = Math.abs(key.hashCode()%ARR_LEN); // 从数组中取出 头结点 Node l = table[index]; // 如果为空，说明第一次添加，创建 if(l == null){ table[index] = new Node(key, value); size++; }else{// 不是第一次添加 // 判断是否有该key Node resNode = get(l,key); // 如果key存在，就替换 if(resNode != null){ resNode.setValue(value); }else{// 不存在就添加到链表 Node newNode = new Node(key,value); addTail(l, newNode); size++; } } } /** * 根据第一个节点Node和key，取出Node的key与该key相同的节点 * @param head * @param key * @return */ private Node get(final Node head,String key){ Node ret = head; while( ret != null ){ if(ret.getKey().equals(key)){ break; } ret = head.getNext(); } return ret; } /** * 添加到链表尾部 * @param node * @param newNode */ private void addTail(final Node node,Node newNode){ Node tail = null; Node temp = node; while( temp != null ){ tail = temp; temp = node.getNext(); } tail.setNext(newNode); } public Object get(String key){ int index = Math.abs(key.hashCode()%ARR_LEN); Node l = table[index]; return get(l, key).getValue(); } public int size(){ return size; } } ``` ### 测试类 ``` package testmap; import java.util.Date; import java.util.HashMap; public class Test { public static void main1(String[] args) { MyHashTable mht = new MyHashTable(); // System.out.println("重地".hashCode()); // System.out.println("通话".hashCode()); mht.put("name", "李雷"); mht.put("set", "男"); mht.put("length", 1.82); mht.put("birthday", new Date()); mht.put("age", 20); mht.put("name", "韩梅梅"); mht.put("name", "lucy"); mht.put("重地", "123"); mht.put("通话", "456"); System.out.println(mht.get("name")); System.out.println(mht.get("set")); System.out.println(mht.get("length")); System.out.println(mht.get("birthday")); System.out.println(mht.get("age")); System.out.println(mht.get("重地")); System.out.println(mht.get("通话")); System.out.println(mht.size() ); } public static void main(String[] args) { HashMap hm = new HashMap(); hm.put("", ""); } } ``` 原文出处：http://malaoshi.top/show_1IX3bYvbc1jh.html