Java中说一下HashMap的实现原理?

1、 HashMap 概述： HashMap 是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
2、 HashMap 的数据结构：在 Java 编程语言中，最基本的结构就是两种，一个是数组，另外一个是模拟指针（引用），所有的数据结构都可以用这两个基本结构来构造的，HashMap 也不例外。HashMap 实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
HashMap 基于 Hash 算法实现的
1、当我们往 HashMap 中 put 元素时，利用 key 的 hashCode 重新 hash 计算出当前对象的元素在数组中的下标
2、存储时，如果出现 hash 值相同的 key，此时有两种情况。
如果 key 相同，则覆盖原始值；
如果 key 不同（出现冲突），则将当前的 key-value 放入链表中
3、获取时，直接找到 hash 值对应的下标，在进一步判断 key 是否相同，从而找到对应值。
4、理解了以上过程就不难明白 HashMap 是如何解决 hash 冲突的问题，核心就是使用了数组的存储方式，然后将冲突的 key 的对象放入链表中，一旦发现冲突就在链表中做进一步的对比。
需要注意 Jdk 1.8 中对 HashMap 的实现做了优化，当链表中的节点数据超过八个之后，该链表会转为红黑树来提高查询效率，从原来的 O(n)到 O(logn)