java HashMap实现原理

java版本:1.8

HashMap结构

Hash(散列函数),一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射, pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不同的输入可能会散列成相同的输出,所以不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HashMap中每个节点的数据结构如下,是一个单向链表结构。

1
2
3
4
5
6
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//hash值
final K key;
V value;
Node<K,V> next;
}

HashMap是用一个Node数组来存储数据,数组的每一值都可以存储一个单向链表,如图所示:

存储过程

1.计算key的hash值
2.通过hash值计算出这个key应该放到Node[] table中的位置
3.判断此位置是否已经存在node,如果不存在,直接可以保存在这个位置,如果存在需要判断当前位置的key和要新增的key是否相同,如果相同则会把value覆盖,如果不相同,则根据当前位置的next找到下一个节点,再进行判断上述过程,直到把此key和value存进去。

获取数据和上述的存储数据过程类似

HashMap的属性

1.Set<Map.Entry<K,V>> entrySet;
用于所有获取key和value键值对。
2.int size;
键值对的数量,
3.final float loadFactor;
装载因子,默认是0.75f,表示HashMap的满的程度。
4.int threshold;
阈值,threshold=capacity*loadFactor;capacity(容量)默认是16,当size大于threshold时,会扩大HashMap的threshold

优点

hash算法将key散落到固定长度的数组中,当数据非常多的时候,随机访问速度依然很快。

坚持原创技术分享,您的支持将鼓励我继续创作!
显示 Gitment 评论