哈希表（散列表）的数据结构

HashMap

1.HashMap集合底层是哈希表（散列表）的数据结构，哈希表是一个数组（长于查询）和单向链表（长于增删）的集合体，拥有数组和链表的优点

2.HashMap集合底层的源代码：

public class HashMap{
            //HashMap底层实际上是一个数组（一维数组）
            Node<K,V> table;
            
            //静态内部类HashMap.Node
            static class Node<K,V>{
                final int hash;//哈希值（哈希值是key的hashCode()方法的执行结果，hash值通过哈希算法可以转换成数组的下标）
                final K key; //存储到Map集合中的那个key
                V value; //存储到Map集合中的那个value
                Node<K,V>next; //下一个节点的内存地址
            }
        }
        
        哈希表（散列表）:一维数组，这个数组中每一个元素是一个单向链表

注：哈希表（散列表）:一维数组，这个数组中每一个元素是一个单向链表

3.put方法原理

注：同一个单向链表上所有节点的hash值相同，因为他们的数组下标是一样的。但是k和k的equals方法肯定返回的是false，都不相等。

4.get方法原理

5.总结：

思考：为什么放在HashMap集合key部分的元素需要重写equals()方法？

原因：因为equals默认比较的是两个对象的内存地址，但是这里需要比较内容是否一样.！！

6.HashMap集合key部分的特点

　　无序，不可重复。

　　无序的原因：增加的数据不一定挂到哪个单向链表上

　　不可重复原因：equals方法保证HashMap集合的key不可重复，如果key重复了value会覆盖掉。

　　注：放在HashMap集合key部分的元素其实就是放到HashSet集合中了，所以HashSet集合中的元素需要同时重写HashCode()和equals()方法。

7.重写HashCode()方法时注意的事项

8.HashMap集合的默认初始化容量是16，默认加载因子是0.75，默认加载因子是当HashMap集合底层数组的容量达到0.75的时候，数组开始扩容。

注：HashMap集合初始化容量必须是2的倍数，这样可以达到散列均匀。

哈希表（散列表）的数据结构

原文：https://www.cnblogs.com/Leeyoung888/p/14284689.html