手写JDK1.7HasMap集合简易版本
手写JDK1.7HasMap集合简易版本
为了加深自己对HashMap集合的理解，参考一些资料，实现一个简易版本的HashMap，为了加深印象和梳理。
HashMap的介绍
从底层结构、put和get方法、hash数组索引、扩容机制等几个方面来分析HashMap的实现原理：
底层结构
HashMap的底层结构是由数组+链表构成的
数组：hash数组（桶），数组元素是每个链表的头节点
链表：解决hash冲突，不同的key映射到了数组的同一索引处，则形成链表
put和get方法
put()方法大概过程如下：
如果添加的key值为null，那么将该键值对添加到数组索引为0的链表中，不一定是链表的首节点。
如果添加的key不为null，则根据key计算数组索引的位置：
数组索引处存在链表，则遍历该链表，如果发现key已经存在，那么将新的value值替换旧的value值
数组索引处不存在链表，将该key-value添加到此处，成为头节点
get()方法的大概过程：
- 如果key为null，那么在数组索引table[0]处的链表中遍历查找key为null的value
- 如果key不为null，根据key找到数组索引位置处的链表，遍历查找key的value，找到返回value，若没找到则返回null
扩容机制
先看一个例子，创建一个HashMap，初始容量默认为16，负载因子默认为0.75，那么什么时候它会扩容呢？
来看以下公式：
实际容量 = 初始容量 × 负载因子
1
计算可知，16×0.75=12，也就是当实际容量超过12时，这个HashMap就会扩容。
初始容量
当构造一个hashmap时，初始容量设为不小于指定容量的2的次方的一个数（new HashMap(5)， 指定容量为5，那么实际初始容量为8，2^3=8>5），且最大值不能超过2的30次方。
负载因子
负载因子是哈希数组在其容量自动增加之前可以达到多满的一种尺度。（时间与空间的折衷） 当哈希数组中的条目数超出了加载因子与初始容量的乘积时，则要对该哈希数组进行扩容操作（即resize）。
特点：
116=16
0.7516=12 0.5*16=8 负载因子越小， 容易扩容—容易扩容的时候 产生新的空数组位置
三次扩容
负载因子1 负载因子0.75 负载因子0.5
1.162=32 16 1.162=32 12 162=32 8
2.322=64 32 2.322=64 24 322=64 16
2.642=128 64 3.642=128 48 64*2=128 32
存放数据10000万个 >13毫秒 存放数据10000万个 13毫秒 存放数据10000万个 21毫秒
存放数据10000万个 76左右毫秒 存放数据10000万个 77左右毫秒
负载因子越小，容易扩容，浪费空间，但查找效率高 链表特别短 减少hash冲突
负载因子越大，不易扩容，对空间的利用更加充分，查找效率低（链表拉长）hash冲突比较多，链表比较长
扩容过程
HashMap在扩容时，新数组的容量将是原来的2倍，由于容量发生变化，原有的每个元素需要重新计算数组索引Index，再存放到新数组中去，这就是所谓的rehash。
eqauls方法和hashCode方法
1 如果两个对象相同，那么它们的hashCode值一定要相同。也告诉我们重写equals方法，一定要重写hashCode方法，也就是说hashCode值要和类中的成员变量挂上钩，对象相同–>成员变量相同—->hashCode值一定相同。
2 如果两个对象的hashCode相同，它们并不一定相同，这里的对象相同指的是用eqauls方法比较。
基于JDK1.7版本实现HashMap
1、自定义一个ExtMap集合接口
package com.zzw.hashmap;
/**
* @author zzw
* @version 1.0
* @description 自定义一个ExtMap集合接口
* @modifiedBy
*/
public interface ExtMap<K,V> {
/*
* @author zzw
* @description 向集合中插入数据
* @params K键 ，V值
* @return V值
**/
V put(K k,V v);
/*
* @author zzw
* @description 根据键值K 从Map集合中查询元素
* @params * K 键值
* @return V值
**/
V get(K k);
/*
* @author zzw
* @description 获取集合元素个数
* @params *
* @return
**/
int size();
// Entry的作用=== Node节点
interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
}
}
2、自定义实现HashMap集合
package com.zzw.hashmap;
/**
* @author zzw
* @version 1.0
* @description 自定义实现HashMap集合
* @modifiedBy
*/
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 k, V v) {
// 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(k, DEFAULT_INITIAL_CAPACITY);
Node<K, V> node = table[index];
if (node == null) {
// 没有发生hash冲突问题--- index冲突
node = new Node<K, V>(k, v, null);
size++;
} else {
Node<K, V> newNode = node;
while (newNode != null) {
// 已经发生hash冲突问题key 直接添加(冲突node)到前面了 不是往后面加
if (newNode.getKey().equals(k) || newNode.getKey() == k) {
// hashCodoe 相同，而且equals 相等情况 说明是同一个对象 修改值
// node.value = value;
return newNode.setValue(v);
} else {
// 继续添加，排在前面 hascode 取模余数相同 index 存放在链表 或者hashCode 相同但是对象不同
// 新的node 的next 原来的node
if (newNode.next == null) {
// 说明遍历到最后一个node ,添加node
node = new Node<K, V>(k, v, node);
size++;
}
}
newNode = newNode.next;
}
}
table[index] = node;
return null;
}
public V get(K k) {
Node<K, V> node = getNode(table[getIndex(k, DEFAULT_INITIAL_CAPACITY)], k);
return node == null ? null : node.value;
}
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;
}
}
/*
* @author zzw
* @description
* @params
* @return
**/
private 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;
}
/*
* @author zzw
* @description 对table进行扩容
* @params
* @return
**/
private void resize() {
// 1.生成新的table 是之前的两倍的大小 DEFAULT_INITIAL_CAPACITY*2
Node<K, V>[] newTable = new Node[DEFAULT_INITIAL_CAPACITY << 1];
// 2.重新计算index索引,存放在新的table里面
for (int i = 0; i < table.length; i++) {
// 存放在之前的table 原来的node
Node<K, V> oldNode = table[i];
// a 的index=1 b 的index=1
// a ##
while (oldNode != null) {
table[i] = null;// 赋值为null---为了垃圾回收机制能够回收 将之前的node删除
// 存放在之前的table 原来的node key
K oldK = oldNode.key;
// 重新计算index
int index = getIndex(oldK, newTable.length);
// 存放在之前的table 原来的node next
if (oldK.equals("22号") || oldK.equals("66号")) {
System.out.println("日志记录");
}
Node<K, V> oldNext = oldNode.next;
// 如果ndex 下标在新newTable发生相同的index时候,以链表进行存储 //
// 原来的node的下一个是最新的（原来的node存放下新的node下一个）
oldNode.next = newTable[index];
// 将之前的node赋值给 newTable[index]
newTable[index] = oldNode;
// 判断是否继续循环遍历
oldNode = oldNext;
}
}
// 3.将newtable赋值给老的table
table = newTable;
DEFAULT_INITIAL_CAPACITY = newTable.length;
newTable = null;/// 赋值为null---为了垃圾回收机制能够回收
}
/*
* @author zzw
* @description 计算获取index键值
* @params K值，length数组长度
* @return index键值
**/
public int getIndex(K k, int length) {
int hashCode = k.hashCode();
int index = hashCode % length;
return index;
}
// 测试方法.打印所有的链表元素
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() + "]");
node = node.next;
// if (node.next != null) {
// node = node.next;
// } else {
// // 结束循环
// node = null;
// }
}
System.out.println();
}
}
}
3、测试用例
/**
* @author zzw
* @version 1.0
* @description ${description}
* @modifiedBy
*/
public class Test {
public static void main(String[] args) {
ExtHashMap extHashMap = new ExtHashMap<String, String>();
extHashMap.put("1号", "1号");// 0
extHashMap.put("2号", "1号");// 1
extHashMap.put("3号", "1号");// 2
extHashMap.put("4号", "1号");// 3
extHashMap.put("6号", "1号");// 4
extHashMap.put("7号", "1号");
extHashMap.put("14号", "1号");
extHashMap.put("22号", "1号");
extHashMap.put("26号", "1号");
extHashMap.put("27号", "1号");
extHashMap.put("28号", "1号");
extHashMap.put("66号", "66");
extHashMap.put("30号", "1号");
System.out.println("扩容前数据....");
extHashMap.print();
System.out.println("扩容后数据....");
extHashMap.put("31号", "1号");
extHashMap.put("66号", "123466666");
extHashMap.print();
// 修改3号之后
System.out.println(extHashMap.get("66号"));
}
}
4、测试结果
日志记录
扩容前数据....
下标位置[0][ key:7号,value:1号]
下标位置[1][ key:6号,value:1号]
下标位置[2]
下标位置[3][ key:4号,value:1号]
下标位置[4][ key:3号,value:1号]
下标位置[5][ key:2号,value:1号]
下标位置[6][ key:1号,value:1号]
下标位置[7]
下标位置[8]
下标位置[9]
下标位置[10]
下标位置[11]
下标位置[12]
下标位置[13]
下标位置[14]
下标位置[15]
下标位置[16]
下标位置[17][ key:28号,value:1号]
下标位置[18][ key:27号,value:1号]
下标位置[19][ key:26号,value:1号]
下标位置[20][ key:14号,value:1号]
下标位置[21]
下标位置[22]
下标位置[23][ key:66号,value:66][ key:22号,value:1号]
下标位置[24]
下标位置[25]
下标位置[26][ key:30号,value:1号]
下标位置[27]
下标位置[28]
下标位置[29]
下标位置[30]
下标位置[31]
扩容后数据....
下标位置[0][ key:7号,value:1号]
下标位置[1][ key:6号,value:1号]
下标位置[2]
下标位置[3][ key:4号,value:1号]
下标位置[4][ key:3号,value:1号]
下标位置[5][ key:2号,value:1号]
下标位置[6][ key:1号,value:1号]
下标位置[7]
下标位置[8]
下标位置[9]
下标位置[10]
下标位置[11]
下标位置[12]
下标位置[13]
下标位置[14]
下标位置[15]
下标位置[16]
下标位置[17][ key:28号,value:1号]
下标位置[18][ key:27号,value:1号]
下标位置[19][ key:26号,value:1号]
下标位置[20][ key:14号,value:1号]
下标位置[21]
下标位置[22]
下标位置[23][ key:66号,value:123466666][ key:22号,value:1号]
下标位置[24]
下标位置[25][ key:31号,value:1号]
下标位置[26][ key:30号,value:1号]
下标位置[27]
下标位置[28]
下标位置[29]
下标位置[30]
下标位置[31]
123466666
总结
1、 HashMap只允许一个为null的key。
2、 HashMap的扩容：当前table数组的两倍
3、 HashMap实际能存储的元素个数： capacity * loadFactor
4、 HashMap在扩容的时候，会重新计算hash值，并对hash的位置进行重新排列， 因此，为了效率，尽量给HashMap指定合适的容量，避免多次扩容
5、HashMap 扩容机制 为什么要扩容
因为链表越长，查询效率越低、节点越多会影响效率，链表查询低，最好使用降低Hash碰撞问题（减少index冲突问题 ）
6、扩容数组之后，有什么影响
hashcode相同，但是扩容数组之后发生变化，重新计算index(重新取模index)
jdk1.8红黑树节点：
HashMap在jdk1.7中的实现，采用的数组+链表的方式实现
HashMap子jdk1.8中的实现，采用的是 数组+红黑树方式
区别在于：
a:
jdk.17的HashMap，产生了新的index冲突，插入的位置在链表的头部
jdk1.8的hashMap,产生冲突后，会插入到树的尾部
b:
jdk1.8在实现的时候，会判断链表的长度是否超过了8，如果超过8则将链表的数据结构，转成红黑树结构（这样设计的意义是什么：防止黑客模拟hash值进行攻击，导致链表的长度过长，导致性能下降 ）
扩展
由于对数据结构的了解深度不够，不能够很好的解析出其更底层的原理，如果想要更深入更详细的Map集合的数据结构和实现，推荐一位博主的文章介绍得更详细，供大家阅读。
最新JDK8HashMap实现过程源码分析
https://blog.csdn.net/youngogo/article/details/81267773