jdk1.7-HashMap原理
- jdk1.7-HashMap的简介
- jdk1.7-HashMap实现原理
- 仿写源码
jdk1.7-HashMap的简介
hashMap的初步使用就不一一赘述了，很多文章都能找的到相应的用法，这里主要讲讲hashMapjdk1.7版本和jdk1.8版本有什么区别：
- jdk1.7采用的是数组 单向链表
- jdk1.8采用的是数组 红黑树，红黑树的效率高于单向链表
我们主要讲解的是jdk1.7hashMap，1.8的之后也会更新
这里要说一下，（JavaScript第六版）ES6中map其实和jdk1.7的HashMap的实现原理相当一致，但是缺少了一步扩容。如果有小伙伴能找到ES6中的扩容方法，可以提供一下。
jdk1.7-HashMap实现原理
- hashMap的底层存储结构是数组 链表
- 此处我们将数组想象成一个桶，易于理解
- 根据存入数据的key采用hash算法去计算出一个hash值
- 判断桶是否需要扩容
- 之后再将数据存入桶的相应位置处
仿写源码
根据思路仿写处源码
代码语言：javascript复制public class ExtHashMap<K, V> implements ExtMap<K, V> {
// 定义HashMap底层存储结构。一开始不初始化，懒加载
private Node<K, V>[] table = null;
// 数组扩容的负载因子，当负载因子太小，会造成频繁扩容。负载因子过大导致链表过长
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
// table的初始化容量
private static int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// hashMap的实际长度
private int size;
/**
* @Description:判断key是否相同
*/
private boolean keyEqual(Node node, K k) {
return node.key.equals(k) && node.key == k;
}
/**
* @Description:计算当前key的hash值
*/
private int calculateHash(K k, int length) {
return k.hashCode() % length;
}
/**
* @Description:hashMap进行添加值的方法
*/
public V put(K k, V v) {
// 判断table是否初始化
if (table == null) {
table = new Node[DEFAULT_INITIAL_CAPACITY];
}
// 判断是否需要扩容
if (size >= (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR)) {
resize();
}
// 将新元素添加到数组中
Node newNode = new Node(k, v, null);
// 获取hashCode值，并计算hash值
int hash = calculateHash(k, DEFAULT_INITIAL_CAPACITY);
// 获取table中是否有元素
Node node = table[hash];
if (node == null) {
// 当前table下标处为空，需添加新的链表
table[hash] = newNode;
size ;
} else {
// 当前table下标处具有链表
if (keyEqual(node, k)) {
// key相同的情况下，进行数据覆盖
node.setValue(v);
} else {
// key 不同，需要将元素添加到链表最前端
newNode.next = node;
table[hash] = newNode;
size ;
}
}
return v;
}
/**
* @Description:数组进行扩容的方法
*/
private void resize() {
// 创建新的table,并且进行数组的扩容
Node<K, V>[] newTable = new Node[DEFAULT_INITIAL_CAPACITY << 1];
// 将table中的数据转移到newTable中，同时进行hash重排
for (int i = 0; i < size; i ) {
// 获取老的node
Node oldNode = table[i];
// 避免出现脏数据
table[i] = null;
while (oldNode != null) {
// 获取oldNode的下一个
Node oldNodeNext = oldNode.next;
// 根据新的长度计算新的hash值
int newHash = calculateHash((K) oldNode.key, DEFAULT_INITIAL_CAPACITY << 1);
// 在链表最前面添加oldNode
oldNode.next = newTable[newHash];
newTable[newHash] = oldNode;
oldNode = oldNodeNext;
}
}
// 将newTable赋值给table，并且修改默认长度值
DEFAULT_INITIAL_CAPACITY <<= 1;
table = newTable;
// 方便gc回收
newTable = null;
}
/**
* @Description:hashMap根据key获取value的方法
*/
public V get(K k) {
Node node = getNode(k);
return node == null ? null : (V) node.value;
}
/**
* @Description:根据key获取某个node
*/
public Node getNode(K k) {
// 计算hash值
int hash = calculateHash(k, DEFAULT_INITIAL_CAPACITY);
Node node = table[hash];
while (node != null) {
if (keyEqual(node, k)) {
return node;
}
}
return null;
}
/**
* @Description:返回hashMap的实际长度
*/
public int size() {
return size;
}
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;
}
System.out.println();
}
}
/**
* @Description:节点
*/
class Node<K, V> implements Entry<K, V> {
K key;
V value;
Node<K, V> next;
private Node(K key, V value, Node<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return value;
}
}
}
