Java HashMap原理与实现-马育民老师

# 说明

- JAVA8之前：HashMap 实现方式：数组 + 链表

- JAVA8：HashMap 实现方式：数组 + 链表 + 红黑树

### 实现原理

1. 创建 长度是 16 的数组

2. 使用 `hash()`函数，对 `key` 算出 `hashcode` 值，并对 16 取模，算出的值，就是数组中的位置，将 元素 放入到该位置

3. 但是，**会发生冲突**，原因如下：
 
 - `hash()`函数算出 `hashcode` 值会冲突
 - 由于数组长度是 16，当元素个数超过 16 时，比如会冲突

4. **解决冲突**：数组存的是链表，当冲突时，将元素放入到链表中

下图是 JAVA8的实现方式，当链表长度大于8时，转为红黑树，查询数据更快

[![](/upload/0/0/1IX3bYBmewZQ.png)](/upload/0/0/1IX3bYBa3DsI.png)

### put() 方法实现过程

[![](/upload/0/0/1IX3bYKYtWK3.jpg)](/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("", "");
	}
}
```

原文出处：/show_1IX3bYvbc1jh.html