基于 JDK1.7 版本实现 HashMap

在JDK1.7中是用的“数组+单链表实现的HashMap”。前一篇我用了LinkedList+数组实现,其实本质上差不多,只是没有写扩容这一块的内容,今天来个原生的方式实现HashMap。

首先思考几个问题?


  • Hash冲突怎么解决?
    • 冲突的元素采用链表存储。
      基于 JDK1.7 版本实现 HashMap
  • HashMap扩容机制?
    • 因为如果不进行扩容,当发生hash冲突的时候会在某个位置不断向后生产新的节点。在查询的时候会遍历节点,从而降低了效率.
  • 扩容后会产生什么影响?
    • 你需要重新根据index和数组长度计算hash值,并且进行冲突判断存储。

核心方法图解

因为很多解释都写到注释里面了,就不分模块解释了。????


  • put方法发生流程解说
    基于 JDK1.7 版本实现 HashMap
  • 扩容方法解说

基于 JDK1.7 版本实现 HashMap

几个认识你应该知道


  1. HashMap只允许一个为null的key。
  2. HashMap的扩容:当前table数组的两倍
  3. HashMap实际能存储的元素个数: capacity * loadFactor
  4. HashMap在扩容的时候,会重新计算hash值,并对hash的位置进行重新排列, 因此,为了效率,尽量给HashMap指定合适的容量,避免多次扩容.

上代码✍

/**
 * @author 程序员快乐的秘密
 *
 */
public interface ExtMap<K, V> {
	// 向集合中插入数据
	public V put(K k, V v);

	// 根据k 从Map集合中查询元素
	public V get(K k);

	// 获取集合元素个数
	public int size();

	interface Entry<K, V> {
		K getKey();

		V getValue();

		V setValue(V value);
	}
}

package com.xianglei.ExtHashMap;

/**
 * 
 * @author 程序员快乐的秘密
 *
 * @param <K>
 * @param <V>
 */
public class ExtHashMap<K, V> implements ExtMap<K, V> {

	// 1.定义table 存放HasMap 数组元素 默认是没有初始化容器 懒加载
	Node<K, V>[] table = null;
	// 2. 实际用到table 存储容量 大小
	int size;
	// 3.HashMap默认负载因子,负载因子越小,hash冲突机率越低, 根据每个链表的个数
	float DEFAULT_LOAD_FACTOR = 0.5f;
	// 4.table默认初始大小 16
	static int DEFAULT_INITIAL_CAPACITY = 16; // 16

	public V put(K key, V value) {

		// 1.判断table 数组大小是否为空(如果为空的情况下 ,做初始化操作)
		if (table == null) {
			table = new Node[DEFAULT_INITIAL_CAPACITY];
		}
		// 2. hashMap 扩容机制 为什么要扩容?扩容数组之后,有什么影响? hahsmap 中是从什么时候开始扩容
		// 实际存储大小=负载因子*初始容量=DEFAULT_LOAD_FACTOR0.75*DEFAULT_INITIAL_CAPACITY16=12
		// 如果size>12的时候就需要开始扩容数组,扩容数组大小之前两倍
		if (size > (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY)) {
			// 需要开始对table进行属数组扩容
			resize();
		}

		// 3.计算hash值指定下标位置
		int index = getIndex(key, DEFAULT_INITIAL_CAPACITY);
		Node<K, V> node = table[index];
		if (node == null) {
			// 没有发生hash冲突问题--- index冲突
			node = new Node<K, V>(key, value, null);
			size++;
		} else {

			Node<K, V> newNode = node;
			while (newNode != null) {
				// 已经发生hash冲突问题key 直接添加(冲突node)到前面了 不是往后面加
				if (newNode.getKey().equals(key) || newNode.getKey() == key) {
					// hashCodoe 相同,而且equals 相等情况 说明是同一个对象 修改值
					// node.value = value;
					return newNode.setValue(value);
				} else {
					// 继续添加,排在前面 hascode 取模余数相同 index 存放在链表 或者hashCode 相同但是对象不同
					// 新的node 的next 原来的node
					if (newNode.next == null) {
						// 说明遍历到最后一个node ,添加node 他的next是node
						node = new Node<K, V>(key, value, node);
						size++;
					}

				}
				newNode = newNode.next;
			}

		}
		table[index] = node;
		return null;
	}

	// hashMap数组扩容机制
	private void resize() {

		// 1.定义新的数组元素
		Node[] newTables = new Node[DEFAULT_INITIAL_CAPACITY << 1];
		// 2. 将老的table的key index重新计算下标
		for (int i = 0; i < table.length; i++) {
			// 老的Node节点
			Node<K, V> oldNode = table[i];
			while (oldNode != null) {
				table[i] = null;
				// 重新计算index 索引下标位置
				K oldKey = oldNode.key;
				int index = getIndex(oldKey, newTables.length);
				// 老的next
				Node oldnext = oldNode.next;
				// 判断newTables数组中,是否存在下标相同,如果下标相同则存放在原来的.next
				oldNode.next = newTables[index];
				// 将原来的node赋值给新的node
				newTables[index] = oldNode;
				// 获取下一个节点,判断是否继续循环
				oldNode = oldnext;
			}
		}

	}

	// 测试方法.打印所有的链表元素
	void print() {

		for (int i = 0; i < table.length; i++) {
			Node<K, V> node = table[i];
			System.out.print("下标位置[" + i + "]");
			while (node != null) {
				System.out.print("[ key:" + node.getKey() + ",value:" + node.getValue() + "]");
				if (node.next != null) {
					node = node.next;
				} else {
					// 结束循环
					node = null;
				}

			}
			System.out.println();
		}

	}

	public int getIndex(K k, int length) {
		int hashCode = k.hashCode();
		int index = hashCode % length;
		return index;
	}

	public V get(K k) {

		Node<K, V> node = getNode(table[getIndex(k, DEFAULT_INITIAL_CAPACITY)], k);
		return node == null ? null : node.value;
	}

	public Node<K, V> getNode(Node<K, V> node, K k) {
		while (node != null) {
			if (node.getKey().equals(k)) {
				return node;
			}
			node = node.next;
		}
		return null;
	}

	public int size() {

		return size;
	}

	// 定义节点
	class Node<K, V> implements Entry<K, V> {
		// 存放Map 集合 key
		private K key;
		// 存放Map 集合 value
		private V value;
		// 下一个节点Node
		private Node<K, V> next;

		public Node(K key, V value, Node<K, V> next) {
			super();
			this.key = key;
			this.value = value;
			this.next = next;
		}

		public K getKey() {
			return this.key;
		}

		public V getValue() {
			return this.value;
		}

		public V setValue(V value) {
			// 设置新值的返回老的 值
			V oldValue = this.value;
			this.value = value;
			return oldValue;
		}

	}

	public static void main(String[] args) {

	}

}

附录:

最后,肯定还有一些细枝末节的东西我没有说到,但是总体的思路基本上就如此。另外给大家一个比较完善的HashMap源码分析的博客链接:https://www.cnblogs.com/chengxiao/p/6059914.html 。他有的我就不说了,写的很好,值得参考。