hashmap 哈希桶
时间: 2023-11-08 16:46:51 浏览: 41
HashMap的底层是由一个哈希桶数组组成的。而哈希桶的大小取决于初始化HashMap时指定的初始容量,即bucket数组的大小。比如,如果使用new HashMap(19),那么哈希桶数组的大小将为32,即2^5。
HashMap在第一次进行put操作时才会分配内存并初始化哈希桶数组。当put操作需要添加元素时,HashMap会根据元素的哈希值计算它在哈希桶数组中的位置,并将元素放入对应的位置。
HashMap在负载因子达到0.75f时会进行扩容,即当哈希桶数组中的元素个数达到了容量的75%时会自动扩容。扩容过程会重新计算元素在新的哈希桶中的位置,并将元素重新插入。
当两个对象的哈希值相同时,会发生哈希冲突或碰撞。这意味着它们会被放置在哈希桶数组的同一个位置上的链表中。在这种情况下,HashMap会从对应位置的链表中遍历查找并比较键的值,以获取正确的值对象。
重新调整HashMap大小时存在一个问题,即重新哈希。因为在扩容时,HashMap需要重新计算元素的哈希值,并将元素插入到新的哈希桶数组中。这个过程会导致性能的损耗,并且可能会导致哈希冲突的增加。
另外值得一提的是,HashSet的底层也是用HashMap实现的,它只存储key,其中的val都是Object对象。因此,HashSet也具有哈希桶的特性。您可以通过学习Java中HashMap的源码来深入了解哈希桶的实现原理。
相关问题
hashmap哈希冲突
在使用HashMap时,由于哈希表的大小是有限的,而键的数量是无限的,因此不同的键可能会映射到相同的哈希表索引上,这就是哈希冲突。当发生哈希冲突时,HashMap会在相应的哈希表索引处维护一个链表,将具有相同哈希值的键值对存储在链表中。当需要查找某个键值对时,HashMap会先计算该键的哈希值,然后在相应的哈希表索引处的链表中查找该键值对。
解决哈希冲突的方法有很多种,HashMap底层是通过链表来解决哈希冲突的。当发生哈希冲突时,新的键值对会被插入到相应哈希表索引处的链表的头部,这样可以保证在查找键值对时,能够先找到最新插入的键值对。但是,当链表过长时,会影响HashMap的性能,因此Java 8中引入了红黑树来优化链表过长的情况。
下面是一个演示HashMap哈希冲突的例子:
```java
import java.util.HashMap;
public class HashMapDemo {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>(); map.put("apple", 1);
map.put("banana", 2);
map.put("orange", 3);
map.put("peach", 4);
map.put("grape", 5);
map.put("watermelon", 6);
map.put("pineapple", 7);
map.put("kiwi", 8);
map.put("pear", 9);
map.put("mango", 10);
map.put("strawberry", 11);
map.put("blueberry", 12);
map.put("raspberry", 13);
map.put("blackberry", 14);
map.put("cherry", 15);
map.put("pomegranate", 16);
map.put("apricot", 17);
map.put("plum", 18);
map.put("fig", 19);
map.put("date", 20);
map.put("peach", 21); // 重复插入键"peach"
System.out.println(map);
}
}
```
输出结果为:
```
{orange=3, watermelon=6, grape=5, kiwi=8, pear=9, apple=1, peach=21, fig=19, blackberry=14, blueberry=12, raspberry=13, date=20, pineapple=7, strawberry=11, pomegranate=16, banana=2, plum=18, mango=10, cherry=15}
```
可以看到,由于键"peach"被重复插入,导致原来的键值对被覆盖了。
hashmap哈希表
哈希表(HashMap)是一种数据结构,它将数组和链表结合在一起。在哈希表中,元素通过哈希函数计算出一个存储位置,然后通过数组下标一次定位就可以进行操作。哈希表的主干是一个数组,每个数组元素是一个链表节点,节点中包含了键值对。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* *3* [HashMap及哈希表](https://blog.csdn.net/SuperDream1sd/article/details/112154610)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* [hash表和hashmap](https://blog.csdn.net/lf173089386/article/details/115264233)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]