hashset存储原理
时间: 2023-03-28 18:02:38 浏览: 45
Hashset 存储原理是利用哈希表来实现的,哈希表是一种以键值对形式存储数据的数据结构。在哈希表中,每个键都对应一个唯一的哈希值,这个哈希值可以通过哈希函数计算得出。在存储数据时,先将键通过哈希函数计算出哈希值,然后将数据存储在对应的哈希值位置上。当需要查找数据时,同样通过哈希函数计算出哈希值,然后在对应的哈希值位置上查找数据。由于哈希表的查找速度非常快,所以 Hashset 可以快速地进行数据的查找和去重。
相关问题
hashset实现原理
HashSet 是基于哈希表实现的集合,它继承于 AbstractSet,实现了 Set 接口。HashSet 存储的元素是无序的,且不允许存储重复元素。
HashSet 的实现原理主要依赖于两个重要的概念:哈希函数和哈希冲突解决方法。
1. 哈希函数
哈希函数是将元素映射到哈希表中一个桶的函数。HashSet 中的哈希函数是通过调用元素对象的 hashCode() 方法来得到的。hashCode() 方法返回的是一个 int 值,该值可以作为元素在哈希表中的索引。
2. 哈希冲突解决方法
哈希冲突指的是不同的元素被映射到哈希表的同一个桶中的情况。HashSet 中采用的哈希冲突解决方法是链表法。当元素被映射到某个桶时,如果该桶已经有元素了,则将新元素添加到该桶对应的链表的末尾。
当链表长度达到一定程度时,链表转为红黑树,以提高查询效率。
当元素数量达到一定阈值时,哈希表会自动扩容,重新分配桶的数量,减少哈希冲突的发生,提高查询效率。
以上就是 HashSet 的实现原理。通过哈希函数和哈希冲突解决方法,HashSet 实现了高效的元素存储和查询。
hashset底层原理
HashSet底层实际上是一个HashMap容器,其中的元素是存储在HashMap的key中的,而value则是一个固定的Object对象。当我们向HashSet中添加元素时,HashSet会首先调用元素所在类的hashCode()方法,计算出元素的哈希值。然后根据这个哈希值,通过算法计算出元素在HashSet底层数组中的存放位置。在此位置上,HashSet会判断是否已经存在元素。如果存在,则判断两个元素是否相等,如果相等,则不添加;如果不相等,则采用链表的方式将该元素添加到链表的末尾。如果该位置上不存在元素,则直接将元素添加到该位置上。
举个例子来说明,假设我们向一个空的HashSet中添加两个Person对象p1和p2,它们的哈希值分别为h1和h2。根据算法计算出的位置分别为pos1和pos2。由于HashSet为空,所以直接将p1和p2添加到pos1和pos2的位置上。此时HashSet中的元素为[p1, p2]。当我们修改p1的name属性为"CC"后,再尝试移除p1。HashSet会再次计算p1的哈希值,得到新的位置pos3。由于pos3上已经存在元素p2,所以HashSet会遍历链表,判断是否有相等的元素。由于p1的name属性被修改为"CC",与原来的"AA"不相等,所以p1会被移除。最终HashSet中的元素为[p2]。