hashmap底层存放原理
时间: 2023-11-11 15:52:14 浏览: 35
HashMap是基于哈希表的Map接口的实现。它的底层数据结构是一个数组,数组中的每个元素都是一个链表或红黑树的头节点。当我们向HashMap中添加键值对时,会先通过hash方法计算key的哈希码,然后通过(n-1)& hash 公式得到key在数组中存放的下标。如果该位置上已经有元素,则通过equals方法比较key是否相等,如果相等,则更新对应的value,如果不相等,则将新的键值对添加到链表或红黑树的末尾。
当链表的长度超过一定阈值(默认为8)时,链表会转化为红黑树,这样可以提高查找和插入的效率。当链表的长度小于等于6时,红黑树又会转化为链表,以节省空间。
相关问题
hashmap底层实现原理
HashMap底层实现原理是基于哈希表的。哈希表是一种散列表,它通过把关键字映射到表中一个位置来访问记录,以加快查找的速度。在Java中,HashMap是通过链表和红黑树来实现的。
具体来说,HashMap底层是一个数组,每个元素是一个链表。当需要往HashMap中存储一个键值对时,会根据键的哈希值计算出它在数组中的位置,如果该位置还没有元素,则直接将该键值对存入该位置;如果该位置已经存在元素,则遍历链表,判断是否已经存在相同的键,如果存在则更新对应的值,否则将该键值对存入链表的末尾。
当HashMap中的元素数量达到一定阈值时,会触发扩容操作,此时会重新计算每个元素的位置,并将它们重新存放到新的数组中。
为了提高查询的效率,HashMap还使用了红黑树的优化,当某个位置的链表长度超过一定阈值时,会将该链表转化为红黑树,以提高查询效率。
总的来说,HashMap底层实现原理是基于哈希表的,通过哈希值计算和链表/红黑树来实现快速存储和查询。
hashmap底层原理
HashMap底层原理是基于数组和链表实现的,具体过程如下:
1. 创建一个数组,数组长度为2的n次幂,例如16、32等。
2. 将key通过hash函数映射为一个整型值,然后对数组长度取模,得到该key应该存放在数组中的位置(下标)。
3. 如果该位置没有元素,则将key-value对直接存入该位置;如果该位置已经有元素,则需要遍历该位置的链表,看是否已经存在该key,如果存在,则更新其value值,否则在链表尾部添加该key-value对。
4. 当链表长度达到一定阈值(8)时,会将链表转化为红黑树,从而提高查询效率。
5. 在添加或删除元素时,需要重新计算所有元素的位置,因为数组长度为2的n次幂,所以只需要进行位运算即可。
6. 当数组中元素数量达到一定阈值(0.75*数组长度)时,会进行扩容操作,将数组长度扩大为原来的两倍,同时需要重新计算所有元素的位置。
7. 在查询元素时,先将key通过hash函数计算出在数组中的位置,然后再遍历该位置的链表或红黑树,查找对应的value值。
总的来说,HashMap底层原理就是通过数组和链表(或红黑树)实现的,通过hash函数将key映射为一个整型值,在数组中存放对应的value值,从而实现高效的添加、删除和查询操作。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)