面渣逆袭

一、Java集合篇

2024/1/22

• 哈希冲突的解决方案：

  哈希冲突是指输入两个不同的值，通过同一个哈希函数，得到一个相同的值；而HashMap是通过链表的方式来解决哈希冲突；

  • 链地址法：在冲突的位置拉一个链表，把冲突的元素放进去；

  • 开放定址法: 从冲突的位置上接着往下找，给冲突元素找个空位

• HashMap的数据结构：

  • jdk8:采用的是：数组+链表+红黑树

  • 数组用于储存数据，链表用于解决哈希冲突，红黑树用于提高查询的效率

• HashMap扩容机制？何时进行扩容？扩容因子为什么是0.75？

  • 为了减少哈希冲突，当hashmap的元素个数达到临界值时，就触发扩容机制

  • 临界值=默认容量*默认扩容因子

  • hashmap初始默认容量为16，初始化容量是2的次幂，扩容之后的长度是之前的2倍，新的容量也是2的次幂，所以扩容机制是随着元素的增加，HashMap通过增大内部数组的容量和重新计算哈希值来保持高效的访问速度。同时，JDK8的优化使得在链表较长时能够通过红黑树提高查询效率。

  • 扩容因子是0.75的原因（扩容因子决定元素的个数达到多少时，方进行扩容）

    • 出于对查询时间和存储空间成本两者之间的平衡考虑

    • 如果扩容因子设置较大时，元素越多，而空位较少的时候才扩容，那么发生查询数据的时间就增加，增大了哈希冲突的概率。

    • 如果扩容因子设置较小，元素越少，而空位较多的时候才扩容，虽然发生哈希冲突的概率降低，查找时间成本降低，但是空间成本增加了，需要更多的空间去存储元素。