详细介绍 HashMap底层原理

数组:其实所谓的数组指的就是一组相关类型的变量集合,并且这些变量彼此之间没有任何的关联 。存储区间连续,占用内存严重,数组有下标,查询数据快,但是增删比较慢;
链表:一种常见的基础数据结构,是一种线性表,但是不会按照线性的顺序存储数据,而是每一个节点里存到下一个节点的指针 。存储区间离散,占用内存比较宽松,使用链表查询比较慢,但是增删比较快;
哈希表:Hash table 既满足了数据的快速查询(根据关键码值key value 而直接进行访问的数据结构),也不会占用太多的内存空间,十分方便 。哈希表是数组加链表组成 。
结构及原理
是基于哈希表的Map接口的非同步实现 。实现对数据的操作,允许有一个null键,多个null值 。
底层就是一个数组结构,数组中的每一项又是一个链表 。数组+链表结构,新建一个的时候,就会初始化一个数组 。Entry就是数组中的元素,每个Entry其实就是一个key-value的键值对,它持有一个指向下一个元素的引用,这就构成了链表,底层将key-value当成一个整体来处理,这个整体就是一个Entry对象 。底层采用一个Entry【】数组来保存所有的key-value键值对,当需要存储一个Entry对象时,会根据hash算法来决定在其数组中的位置,在根据方法决定其在该数组位置上的链表中的存储位置;当需要取出一个Entry对象时,也会根据hash算法找到其在数组中的存储位置,在根据方法从该位置上的链表中取出Entry;
的存储
put:(key-value)方法是中最重要的方法,使用最主要使用的就是put,get两个方法 。
判断键值对数组table[i]是否为空或者为null,否则执行()进行扩容;根据键值key计算hash值得到插入的数组索引 i ,如果table[i] == null,直接新建节点添加即可,转入6,如果table[i] 不为空,则转向3;判断table[i] 的首个元素是否和key一样,如果相同(和)直接覆盖value,否则转向4;判断table[i] 是否为,即table[i]是否为红黑树,如果是红黑树,则直接插入键值对,否则转向5;遍历table[i] ,判断链表长度是否大于8,大于8的话把链表转换成红黑树,进行插入操作,否则进行链表插入操作;便利时遇到相同key直接覆盖value;插入成功后,判断实际存在的键值对数量size是否超过了,如果超过,则扩容;

详细介绍  HashMap底层原理

文章插图
看一下put源码
get方法取值过程:
int hash = key.();
int index = hash%Entry[].;
指定key通过hash函数得到key的hash值;调用内部方法(),得到桶号(一般为hash值对桶数求摸);比较桶的内部元素是否和key相等,如不相等,则没有找到,相等,则取出相等记录的value;如果得到key所在桶的头结点恰好是红黑树节点,就调用红黑树节点的()方法,否则就遍历链表节点 。()方法通过调用树形节点的find()方法进行查找 。由于之前添加时已经保证这个树是有序的,因此查找时基本就是折半查找,效率高;如果对比节点的哈希值和要查找的哈希值相等,就会判断key是否相等,相等就直接返回;不相等就从子树中递归查找;
中直接地址用hash函数生成,冲突用比较函数解决 。如果每个桶内部只有一个元素,那么查找的时候只有一次比较 。当许多桶内没有值得时候,许多查询就会更快
方法
添加新元素前,判断是否需要对map的数组进行扩容,如果需要扩容,则扩容多大?对于新增key-value键值对,如果可以的hash值相同,则构造单向列表;
源码分析:
详细介绍  HashMap底层原理