基于 JDK1.7 版本实现 HashMap
在JDK1.7中是用的“数组+单链表实现的HashMap”。前一篇我用了LinkedList+数组实现,其实本质上差不多,只是没有写扩容这一块的内容,今天来个原生的方式实现HashMap。
首先思考几个问题?
- Hash冲突怎么解决?
- 冲突的元素采用链表存储。
- 冲突的元素采用链表存储。
- HashMap扩容机制?
- 因为如果不进行扩容,当发生hash冲突的时候会在某个位置不断向后生产新的节点。在查询的时候会遍历节点,从而降低了效率.
- 扩容后会产生什么影响?
- 你需要重新根据index和数组长度计算hash值,并且进行冲突判断存储。
核心方法图解
因为很多解释都写到注释里面了,就不分模块解释了。????
-
put方法发生流程解说
- 扩容方法解说
几个认识你应该知道
- HashMap只允许一个为null的key。
- HashMap的扩容:当前table数组的两倍
- HashMap实际能存储的元素个数: capacity * loadFactor
- 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 。他有的我就不说了,写的很好,值得参考。