Java SE面试—Hash Map

本文主要是介绍Java SE面试—Hash Map，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

HashMap底层原理

Put方法

Get方法

哈希冲突

HashMap的扩容

HashMap与HashTable区别

LinkedHashMap

TreeMap

HashMap底层原理

HashMap底层数据结构是数组+链表+红黑树，在1.7之前是数组+链表，由于链表是顺序查询，查询效率低，所以在链表长度大于8的时候，会将链表升级为红黑树

Put方法

1. 当一个键值对插入时，会先根据键通过HasCode()方法计算哈希值，确定键在数组中的桶位置（数组中的每一个元素被称为一个桶）。哈希函数会根据键的哈希码映射到数组的索引位置。

2. 判断这个位置的桶是否为空，若为空，创建一个链表

3. 不为空，则遍历链表或红黑树，判断键是否存在

   存在则更新值

   不存在就将键值对添加到链表尾部或红黑树中

Get方法

1. 通过HashCode()方法计算键的哈希值，并通过哈希函数映射到数组的索引位置

2. 根据哈希值定位到数组的桶位置

3. 遍历桶中的链表或红黑树，存在返回值，不存在返回null

哈希冲突

• 哈希冲突是指不同的键通过哈希函数计算出的哈希值相同，表示应该存在相同的数组位置

• 解决哈希冲突的四种方法

1. 链地址法，采用数组+链表+红黑树的形式

2. 开放地址法，当发生哈希冲突时，用方法计算间隔，将键存放到当前位置的一定间隔后

   1. 设置一个固定的间隔

   2. 通过函数计算间隔

   3. 通过哈希函数计算间隔

3. 再哈希法，当发生哈希冲突时，对键再次进行哈希计算

4. 公共溢出区法，设置一个溢出区，发生冲突的键存放到溢出区中。通常配合桶使用，在基本表中一定间隔设置一个桶。溢出区存满则会进行扩容

HashMap的扩容

• 触发条件

  • 存入的元素个数>槽位数（数组长度） * 负载因子（默认0.75）时，会扩容（扩容为原来的2倍），创建新的hash表，将元素移动到新的hash表中

  • 扩容后会重新计算哈希值

HashMap与HashTable区别

1. 线程安全

   • HashMap是线程不安全的，当多个线程同时对一个HashMap进行读写操作的时候，可能会导致数据不一致

2. 空键和空值

   • HashMap支持键和值存入null，但是只能有一个键为nul

3. 继承关系

   • HashMap实现了Map接口

   • HashTable是继承一个古老的类(Dictionary )

4. 性能

   • 在单线程环境下或者通过外部同步机制保证线程安全的情况下，性能通常比 Hashtable 更好

   • HashTable由于线程安全的特性，性能较低

LinkedHashMap

• 底层原理是哈希表

• 有序，不重复，无索引

TreeMap

• 底层原理是红黑树

• 不重复，无索引，可排序（键）

这篇关于Java SE面试—Hash Map的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---