HashMap集合：

1、HashMap集合底层是哈希表/散列表的数据结构

图解哈希表（引自b站老杜javase）：

自平衡二叉树结构：

2、哈希表是一个怎样的数据结构？

• 哈希表是一个数组和单向链表的结合体

• 数组：在查询方面效率很高，随机增删效率方面效率很低

• 单向链表：在随机增删方面效率较高，在查询方面效率很低

• 哈希表将以上的两种数据结构融合在一起，充分发挥它们的特点

3、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;//下一个节点的内存地址

}

}

哈希表/散列表：一维数组，这个数组中每一个元素是一个单向链表。（数组和链表的结合）

4、最主要掌握的是：

map.put(k,v)

v = map.get(k)

以上这两个方法的实现原理，掌握

5、HashMap集合的key部分特点：

• 无序，不可重复。

• 为什么无序？因为不一定挂到哪个单向链表上

• 不可重复是怎么保证的？equals方法来保证HashMap集合的key不可重复

• 如果key重复了，values会覆盖

• 放在HashMap集合key部分元素其实就是放到HashSet集合中了

• 所以HashSet集合中的元素也需要同时重写hashCode()+equals()方法。

  • 7 % 4 = 3，11 % 4 = 3（hash值不同时，通过hash算法转换的下标有可能一样，所以必须重写hashCode方法，Object中的hashCode方法返回对象的内存地址转换成hash值）

6、哈希表HashMap使用不当时无法发挥性能！

• 假设将所有的hashCode（）方法返回值固定为某个值，那么会导致底层哈希表变成了纯单向链表。这种情况我们称为：散列分布不均匀

• 什么是散列分布不均匀？

  • 假设有100个元素，10个单向链表，那么每个单向链表上有10个节点，这是最好的。是散列分布均匀的
  • 假设将多有的hashCode（）方法返回值都设定为不一样的值，可以吗？有什么问题？不行，因为这样的话导致底层哈希表就成为一维数组了，没有链表的概念也是散列分布不均匀

散列分布均匀需要你重写hashCode（）方法时有一定的技巧

7、重点：

放在HashMap集合key部分的元素，以及放在HashSet集合中的元素，需要同时重写hashCode和equals方法

8、HashMap集合的默认初始化容量是16，默认加载因子是0.75

• 这个默认加载因子是当HashMap集合底层数组的容量达到是75%的时候，数组开始扩容

• 重点，记住：HashMap集合初始化容量必须是2的倍数，这也是官方推荐的。这是因为达到散列均匀，为了提高HashMap集合的存取效率，所必须的。

示例代码01：

public class HashMapTest01 {
    public static void main(String[] args) {

        //创建HashMap集合对象
        //测试HashMap集合key部分的元素特点的
        //Integer是key，它的hashCode和equals都重写了
        Map<Integer,String> map = new HashMap<>();

        //往集合中添加元素
        map.put(1111,"zhangsan");
        map.put(6666,"lisi");
        map.put(7777,"wangwu");
        map.put(2222,"zhaoliu");
        map.put(2222,"zhaoliu");//key重复的时候value会自动覆盖

        //遍历集合
        Set<Map.Entry<Integer, String>> set = map.entrySet();
        for(Map.Entry<Integer, String> entry : set){
            //验证结果：HashMap集合key部分元素：无序不可重复
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }


    }
}

运行结果：

9、向Map集合中存，以及从Map集合中取

都是先调用key的hashCode方法，然后再调用equals方法！

equals方法有可能调用，也有可能不调用。

拿put（k,v）举例，什么时候equals不会调用？

• k.hashCode()方法返回哈希值，哈希值经过哈希算法转换成数组下标，
• 数组下标位置上如果是null，equals不需要执行

拿get（k）举例，什么时候equals不会调用？

• k.hashCode()方法返回哈希值，哈希值经过哈希算法转换成数组下标
• 数组下标位置上如果是null，equals不需要执行

10、注意：如果一个类的equals方法重写了，那么hashCode（）方法必须重写

并且equals方法返回如果是true，hashCode（）方法返回的值必须一样

equals方法返回true表示两个对象相同，在同一个区链表上比较

那么对于同一个单向链表上的节点来说，他们的哈希值都是相同的

所以hashCode（）方法的返回值也应该相同

hashCode()方法和equals方法不用研究，直接使用IDEA工具生成，但是两个方法要同时生成

11、终极结论：

放在HashMap集合key部分的，以及放在HashSet集合中的元素，需要同时重写hashCode方法和equals方法

12、对于哈希表数据结构来说：

如果o1和o2的hash值相同，一定是放到同一个单向链表上

当然如果o1和o2的hash值不同，但由于哈希算法执行结束之后转换的数组下标可能相同，此时会发生“哈希碰撞”
jdk7HashMap底层数据结构是数组 + 链表
jdk8HashMap底层数据结构是数据 + 链表 + 红黑树
当数组长度>64并且链表中的元素个数>8时，链表转换成红黑树结构
当红黑树中的节点个数<6时，红黑树转换成链表结构

示例代码02：

public class HashMapTest02 {
    public static void main(String[] args) {

        Student s1 = new Student("zhagnsan");
        Student s2 = new Student("zhagnsan");

        System.out.println(s1.equals(s2));//没重写equals之前是false，重写之后是true

        //输出两个对象的hash值
        System.out.println("s1的哈希值是：" + s1.hashCode());//1163157884
        System.out.println("s1的哈希值是：" + s2.hashCode());//1956725890

        //创建HashSet集合对象
        // s1.equals(s2)结果已经是true了，表示s1和s2是一样的，相同的，那么往HashSet集合中放的话，
        // 按说只能放进去1个。（HashSet集合特点：无序不可重复）
        Set<Student> students = new HashSet<>();// 这个结果按说应该是1. 但是结果是2.显然不符合HashSet集合存储特点。怎么办？
        students.add(s1);
        students.add(s2);
        System.out.println(students.size());
    }
}
运行结果：
true
s1的哈希值是：1163157884
s1的哈希值是：1956725890
2

13.HashMap集合key部分允许null吗？

允许
但是要注意：HashMap集合的key null值只能有一个。

示例代码03：

public class HashMapTest03 {
    public static void main(String[] args) {

        Map map = new HashMap();

        //向集合中添加null的key和value
        map.put(null,null);
        System.out.println(map.size());//1
        //再次向集合中添加null的value，和不为null的key
        map.put(null,100);
        System.out.println(map.size());//1

        //通过key获取value
        System.out.println(map.get(null));//100

    }
}