深入HashSet、HashMap集合

一、哈希表数据结构

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希表是数组和单向链表的结合体。哈希表实际上是一个一维数组，数组中的每个元素是一个单向链表。

数组：查询效率高，随机增删效率低。

单向链表：随机增删效率高，查询效率低。哈希表将以上两种数据结构结合在一起，充分发挥它们各自的优点。

哈希表数据结构

二、HashMap集合 

(1) HashMap集合概述

HashMap集合底层是哈希表/散列表的数据结构，哈希表底层其实是一个存储元素为单向链表的一维数组。

键(key)不可以重复，而值(value)可以重复。

允许key为null(null键只有一个，并存于数组的第一位置)，value为null(key不同，value可多个)。

线程不安全，效率高。

无序集合（添加顺序，迭代顺序不一致）。

不能存在重复元素（得益与hashCode算法和equals()方法）。

集合中的元素以 "key=value" 键值对的方式保存在数组中。

其中 key 和 value 被包装成一个对象存入数组中，这个对象的类型就是Map接口中的静态内部类 Node<K,V>，这个内部类实现了Map.Entry<K,V>接口。static class Node<K,V> implements Map.Entry<K,V>

(2) HashMap集合的基本操作

public class HashMapTest01 {
    public static void main(String[] args) {
        //Integer是key，它重写hashCode()和equals()方法
        //String是value，它重写hashCode()和equals()方法
        //创建HashMap集合;
        Map<Integer,String> map = new HashMap<>();

        //元素添加;
        map.put(111,"张三");
        map.put(666,"李四");
        map.put(777,"王五");
        map.put(222,"赵六");
        map.put(222,"孙七");

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

        //判断集合中是否包含某个key
        System.out.println(map.containsKey(111));

        //判断集合中是否包含某个value
        System.out.println(map.containsValue("友人A"));

        //key重复的value会覆盖
        System.out.println(map.size());

        //判断集合是否为空
        System.out.println(map.isEmpty());

        //通过 key 删除键值对
        map.remove(222);

        //获取集合中键值对的个数
        System.out.println(map.size());

        //遍历1
        //通过Map集合中的所有key,所有key是一个set集合。
        //通过遍历set集合中的key，来遍历HashMap集合
        Set<Integer> keys = map.keySet();

        for (Integer key:keys) {
            System.out.println(key+"="+map.get(key));
        }

        Iterator<Integer> it = keys.iterator();
        while (it.hasNext()){
            int key = it.next();
            System.out.println(key+"="+map.get(key));
        }

        //遍历2
        //将map集合转为Set集合，Set元素集合元素的类型是Map.Entry<Integer,String>
        Set<Map.Entry<Integer,String>> node = map.entrySet();
        Iterator<Map.Entry<Integer,String>> it1 = node.iterator();
        while (it1.hasNext()){
            System.out.println(it1.next());
        }

        for (Map.Entry<Integer,String> kv:node) {
            System.out.println(kv);
        }
        
    }
}
           

(3) HashMap集合的存取原理

① 为啥哈希表的随机增删，以及查询效率都很高?

增删是在链表上完成的，查询也不需要全部扫描，只需要部分扫描。

② HashMap集合如何保证无序不可重复

无序？通过哈希算法将hashCode()方法计算出来的哈希值转为数组下标，所以不一定挂在哪个单向链表上。

不可重复？equals()方法保证了HashMap集合的key不可重复，因为如果key重复了，value会被覆盖

放到HashMap集合Key部分的元素，其实就是放到HashSet集合中了，所以HashSet集合中的元素也要同时重写hashCode()和equals()方法

③ 哈希表HashMap使用不当时无法发挥其性能

1. 重写hashCode()方法，所有的hashCode()方法返回一个固定值可以吗？

    不能，如果返回一个固定值，那么会导致底层哈希表变成纯单向链表。

    这种情况，我们称为散列分布不均匀。

2. 重写hashCode()方法，所有的hashCode()方法返回不一样的值，可以吗？

    不能，如果每个hashCode()方法返回不一样的值，那么会导致底层哈希表变成存一维数组，没有链表的概念了。

    也是散列分布不均匀。

散列分布均匀：要你重写hashCode()方法时有一定的技巧。

④ 重点：放在HashMap集合key部分的元素，和HashSet集合中的元素，需要重写hashCode()和equals()方法。

⑤ HashMap默认初始化容量16，默认加载因子值0.75【当底层数组容量到大75%的时候，数组开始扩容】。

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

(4) 重写 equals() 方法 和 hashCode() 方法

1. 向Map集合中存元素，以及从Map集合中取元素，都是先调用key的hashCode()方法，然后调用equals()方法.equals()方法可能调用，也可能不调用。
2. equals()方法什么时候不调用？k.hashCode()方法返回哈希值，哈希值转换为数组下标。数组下标的位置上如果是null，equals不需要执行。
3. 在HashMap集合中，对于同一链表上的节点来说，它们的哈希值是相同的，也有不同的情况(哈希碰撞)，但最终通过哈希算法计算出来的数组下标是一样的。哈希值相同，一定在同一链表上！
4.  hashCode()、equals()方法用idea同时生成
5. 在JDK8之后，如果哈希表单向链表中元素超过8个，单向链表这种数据结构就会变成红黑树数据结构，当红黑树上的节点数量小于6时，会把红黑树变成单向链表数据结构。这是因为树的查询效率比链表高，提高了检索效率。

public class HashMapTest02 {
    public static void main(String[] args) {
        Student st1 = new Student("张三");
        Student st2 = new Student("张三");
        /*重写equals()方法之前是false
        System.out.println(st1.equals(st2));
        */
        //重写equals()方法之前是true
        System.out.println(st1.equals(st2));

        /*重写hashCode()方法之前，两个哈希值不一样
        System.out.println("s1的hashCode"+st1.hashCode());
        System.out.println("s2的hashCode"+st2.hashCode());
         */

        //重写hashCode()方法之后，两个哈希值一样
        System.out.println("s1的hashCode"+st1.hashCode());
        System.out.println("s2的hashCode"+st2.hashCode());

      /*重写hashCode()方法之前，因为哈希值不一样，虽然equals()方法返回的是true，
        按说st1 和 st2 只能放进去一个(HashSet集合特点：无序不可重复)。
        但结果却是两个一样的元素都放进去了。：原因是因为这两个的对象的哈希值
        不同，导致了放到数组中的不同下标，这样就没有执行equals()方法比较了。
        因为执行原理是先执行hashCode()方法,在执行equals()方法。
        Set<Student> set = new HashSet<>();
        set.add(st1);
        set.add(st2);
        System.out.println(set.size());//2
      */

      //重写了hashCode()方法
        Set<Student> set = new HashSet<>();
        set.add(st1);
        set.add(st2);
        System.out.println(set.size());//1
    }
}