Map和Set

Map和Set是一种专门用来搜索的数据结构。这俩都是接口，并不是具体实现类。

模型

一般把搜索的数据称为关键字(Key)，把与关键字对应的称为值(Value)，将其称为Key-Value键值对，产生两种模型：

纯Key模型：比如存储英文单词，对应的是Set接口。

Key-Value模型：比如要存储英文单词，以及单词对应的出现次数。对应的是Map接口。

Map

1️⃣Map是一个接口，不能直接new对象，可以new其实现类：TreeMap，HashMap

2️⃣Map中的key不可以重复，value可以重复，如果添加的键值对中的key重复了，会覆盖掉原有的键值对

3️⃣Map中键值对的key不能直接修改，value可以修改，如果要修改key，需要将键值对删除掉，再添加新的键值对

4️⃣TreeMap和HashMap的对比：TreeMap关于key有序，HashMap无序；TreeMap中存储的元素必须是可比较的，如果是自定义类型，需要传一个比较器。

TreeMap和HashMap对比

Entry<K,V>

Map是一个接口，其中有一个内部接口：

⭕️Entry<K,V>相对于Map<K,V>的关系就相当于Node相对于LinkedList。所以Entry<K,V>是真正存储键值对的。所以当Map的实现类实现了Map接口的时候，实现类中也得有个内部类实现Entry<K,V>接口。

比如TreeMap中的内部类Entry<K,V>：这个内部类其实就是真正存储键值对的节点，

常用方法

Map中的常用方法：

1️⃣V get(Object key)：返回key对应的value，如果key不存在，返回null

2️⃣V getOrDefalult(Object key,V defaultValue)：如果key存在，返回对应的value，如果key不存在，返回defaultValue。

3️⃣V put(K key,V value)：设置一组键值对，如果key在map中已经存在了，则会覆盖掉之前的键值对,并返回旧的键值对的Value（因为Map中Key不能重复）。如果key在map中不存在，返回的是null。

4️⃣V remove(Object key)：删除key及其对应的Value这组键值对，如果原map中有对应的key，则删除并返回对应的value，如果原map中没有对应的value，则返回的是null

5️⃣Set keySet() : 返回所有key的不重复集合：将map中所有的key存储到Set中

6️⃣Collection values()：返回所有value的可重复集合

7️⃣Set<Map.Entry<K,V>> entrySet() : 返回所有的key-value映射关系，返回的是一个集合，集合中的元素是一个个对象，对象中存储的是原map中的key和value

8️⃣boolean containsKey(Object key)：判断map中是否包含key

9️⃣boolean coontainsValue(Object value) :判断map中是否包含value

Set

Set和Map的区别在于Set继承自Collection接口，Set中存储的是Key，Map中存储的是Key-Value

但其实TreeSet和TreeMap底层用的是一样的结构，都是红黑树，HashSet和HashMap底层用的结构是一样的，都是哈希桶。

在源码中：

创建Set实例实际创建的还是Map实例。

1️⃣Set中存储的是Key，Map中存储的是Key-Value，且Set中的key不能有重复的

2️⃣Set实现类：TreeSet和HashSet，TreeSet中key是有序的，HashSet中key是无序的。

3️⃣Set底层是使用的Map

4️⃣Set中的key不能修改，如果要修改需先删除再插入

5️⃣TreeSet中不能插入null，因为插入null无法比较

TreeSet和HashSet对比

常用方法

1️⃣boolean add(E e)：添加元素到集合中，如果集合中有则不添加成功

2️⃣void clear()：清空集合

3️⃣boolean contains(Object o)：判断集合中是否有该元素

4️⃣boolean remove(Object o)：删除集合中的元素

5️⃣int size()：返回set中元素个数

6️⃣ boolean isEmpty(): 返回集合是否为空

7️⃣Object[] toArray()：将集合中的元素转换为数组返回

8️⃣boolean containsAll(Collection<?> c)：判断集合c中的元素是否在set中全部存在，是返回true，否返回false

9️⃣boolean addAll(Collection<? extends E> c)，将集合c中的元素全部添加到set中，还是会保证元素不重复。

OJ练习

只出现一次数字

OJ链接

⭕️==方法一：==使用Set，遍历数组，集合中没有当前数字则进集合，有当前数字则出集合，那最后出现两次的数字就不会在集合中存在，只剩出现一次的数字。

class Solution {
    public int singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i=0;i<nums.length;i++){
            if(set.contains(nums[i])){
                set.remove(nums[i]);
            }else{
                set.add(nums[i]);
            }
        }
        for(Integer x:set){
            return x;
        }
        return 0;
    }
}

⭕️==方法二：==遍历数组，把所有数字按位异或到一个数字num上，num初始为0。

class Solution {
    public int singleNumber(int[] nums) {
        int num = 0;
        for(int i=0;i<nums.length;i++){
            num ^= nums[i];
        }
        return num;
    }
}

复制带随机指针的链表

OJ链接

⭕️==方法一：==使用map存储新旧节点的地址，这样新旧节点的对应关系就保存了下来，后续修改next指针域和random指针域就可以根据map中存储的信息修改。

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        Node cur = head;
        Map<Node,Node> map = new HashMap<>();
        //将旧节点和新节点的地址一一对应存到map中
        while(cur!=null){
            Node node = new Node(cur.val);
            map.put(cur,node);
            cur = cur.next;
        }
        cur = head;
        while(cur!=null){
            //对于HashMap,get的参数是null则返回null
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;                  
        }
        return map.get(head);
    }
}

?时间复杂度：O(N)，空间复杂度：O(N)

⭕️方法二：

1️⃣每创建一个新的节点就插入到链表的旧结点之后，让旧结点和新节点有一一对应关系(前是旧结点，后是新节点)。

2️⃣然后遍历链表，修改新节点的random指针域。这时候先不能修改next指针域，一修改next对应关系就没了。

3️⃣再次遍历链表，将新节点从原链表中一个一个移出，并连接到新链表的最后。

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        Node cur = head;
        //把新的节点加到旧节点之后
        while(cur!=null){
            Node newNode = new Node(cur.val);
            newNode.next = cur.next;
            cur.next = newNode;
            cur = cur.next.next;           
        }
        cur = head;
        //修改radom指针域
        while(cur!=null){
            Node newNode = cur.next;
            Node nextNode = cur.next.next;
            newNode.random = (cur.random == null ? null : cur.random.next); 
            cur = nextNode;  
        }
        //修改next指针域
        cur = head;
        Node newHead = null;
        Node lastNode = null;
        while(cur!=null){
            Node newNode = cur.next;
            Node nextNode = cur.next.next;
            //把新节点从原链表拆下来
            cur.next = nextNode;
            //把拆下来的新节点连接到新链表末尾
            if(newHead == null){
                newHead = newNode;
                lastNode = newHead;
            }else{
                lastNode.next = newNode;
                lastNode = newNode;
            }
            cur = nextNode;
        }
        return newHead;
    }
}

?时间复杂度:O(N)，空间复杂度:O(1)

宝石与石头

OJ链接

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for(int i=0;i<jewels.length();i++){
            set.add(jewels.charAt(i));
        }
        int count = 0;
        for(int i=0;i<stones.length();i++){
            if(set.contains(stones.charAt(i))){
                count++;
            }
        }
        return count;
    }
}

坏键盘打字

OJ链接

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();
        str2 = str2.toUpperCase();
        str1 = str1.toUpperCase();
        Set<Character> set = new HashSet<>();
        for(int i=0;i<str2.length();i++){
            set.add(str2.charAt(i));
        }
        Set<Character> set1 = new HashSet<>();
        for(int i=0;i<str1.length();i++){
            char tmp = str1.charAt(i);
            if(!set.contains(tmp) && !set1.contains(tmp)){
                set1.add(tmp);
                System.out.print(tmp);
            }
        }
    }
}

前K个高频单词

OJ链接

public static List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        for(int i=0;i<words.length;i++){
            String word = words[i];
            if(map.containsKey(word)){
                map.replace(word,map.get(word)+1);
            }else{
                map.put(word,1);
            }
        }
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        PriorityQueue<Map.Entry<String,Integer>> priorityQueue = new PriorityQueue<>(k,new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1,
                               Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        for(Map.Entry<String,Integer> entry:entrySet){
            //
            if(priorityQueue.size()<k){
                priorityQueue.offer(entry);
            }else{
                Map.Entry<String,Integer> top = priorityQueue.peek();
                if(top.getValue().compareTo(entry.getValue()) < 0){
                    priorityQueue.poll();
                    priorityQueue.offer(entry);
                }
                if(top.getValue().compareTo(entry.getValue()) == 0){
                    if(top.getKey().compareTo(entry.getKey()) > 0){
                        priorityQueue.poll();
                        priorityQueue.offer(entry);
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        while(priorityQueue.size() > 0){
            String str = priorityQueue.poll().getKey();
            list.add(str);
        }
        Collections.reverse(list);
        return list;
    }

⭕️查找前K个高频单词，按照频率由高到低返回，如果频率相同，则按字符串的字典序排列。

1️⃣先使用Map记录每个单词出现的次数。

2️⃣map.entrySet得到键值对集合，创建堆，定义好比较规则：单词出现频率是第一比较规则，如果出现频率相同，再按照单词的字典序排序（这是第二比较规则）。堆顶元素应该是当前出现频率最小的元素，且如果当前堆中有多个元素和堆顶元素出现频率相同，堆顶元素的字符串的字典序应该是最后的。因为最后要返回的是频率由高到低排序，且如果频率相同，再按照字典序排序的。

3️⃣当堆中不够K个元素时，就直接入堆，入够K个元素之后，此时按照比较规则，堆顶元素一定是出现频率最小的，如果堆中还有其他元素和堆顶元素频率相同，那堆顶元素应该是字典序靠后的。

4️⃣再接着遍历集合元素，如果当前元素比堆顶元素频率高，则出堆顶元素，入当前元素；如果当前元素和堆顶元素频率一样高，再比较字典序，如果堆顶元素靠后，则出堆顶元素，入当前元素。

5️⃣最终依次出堆顶元素到List中，然后逆序List即可

?本题的关键是保持堆顶元素一直是当前堆中频率最低（如果当前堆中有多个频率最低，则堆顶是字典序靠后的元素）。

哈希表

哈希表又称散列表（HashTable），是一种用于快速查找的数据结构，当查找一个元素时，如果使用数组时间复杂度是O(N)，如果使用二叉搜索树，在好的情况下是O(logN)，那有没有一种数据结构可以达到O(1)的复杂度呢？

答案是有的，这种数据结构就是哈希表。哈希表中主要存储的是键值对。HashMap和HashSet的底层就是哈希表

?哈希表的原理：使用元素的关键码经过哈希函数（又称散列函数）计算得到一个存储位置。让元素和地址经哈希函数建立起对应关系。插入数据到哈希表时根据哈希函数计算地址存储到相应地址，查询元素时再根据哈希函数计算关键码对应的地址，就可以达到O(1)的时间复杂度。

哈希表所用数据结构

哈希表的底层主要是数据，但是不仅是数组，一般实现哈希表，可以有两种方式：

1. 数组+链表      2. 数组+二叉树

为啥不仅使用数组呢？因为拿不同的key计算的hash值可能是一样的，这样两个不同的键值对都要存储到当前下标这个位置，这就叫做哈希冲突或者哈希碰撞。

哈希冲突：计算hash值，再通过hash值得到的下标是一样的，就会发送哈希冲突。如果哈希值一样，那一定会发送冲突，如果哈希值不一样，但是计算出来的下标是一样的，那也会发生哈希冲突。

解决哈希冲突

闭散列

?闭散列也称为开放定址法：当发生哈希冲突时，如果哈希表未填满，就可以去哈希表中找下一个空位置，然后把数据填到这个空位置。那如何寻找下一个空位置呢？

1️⃣线性探测：从发生冲突的位置依次向后探测，寻找下一个空位置。

比如要插入44这个元素，根据哈希函数计算，应该插到4下标处，但是4下标已经存了4，则依次向后找空位置，最终下标8空闲，就存到了下标8处。

线性探测的方式有一定的缺陷：比如要查找44，得从4下标开始一直往后找，直到找到44或者没有找到。效率并不高。插入时也是一样，得一直向后寻找下一个空位置，如果当前下标冲突比较多，那么其实找空位置也是需要一定时间的。

2️⃣二次探测：线性探测找空位置的方法是一个挨着一个去找，二次探测可以理解为跳着去找，找下一个空位置的方法是：

比如14要插入4下标，结果发生哈希冲突了，那寻找下一个下标：（4+1 * 1）%10 = 5 (假如表的大小是10)，如果5位置也冲突了，那再寻找下一个空位置： （4+2 * 2）%10 = 8，如果8下标也冲突了，那再寻找下一个空位置：(4 + 3 * 3)%10=3。

因此二次探测的方法空间利用率比较低，而上面的线性探测的方法时间效率低。那下面就给出更好的方法：开散列

开散列

?开散列也称为哈希桶/开链法：对关键码通过哈希函数计算地址，对于如果地址计算相同的元素放入一个桶中，这个桶其实就是一个链表，然后数组中存储链表头结点。也就是发生哈希冲突的元素处于同一链表中。链表的头结点放在数组中。

哈希桶就是上面这种结构，每个数组元素其实都是一个链表，数组中存放链表头结点。插入元素的时候先计算哈希地址，然后插入对应的链表中。查询元素的时候先计算哈希地址，然后在对应的链表中再找对应元素。

这种方式其实就相当于把一个大集合拆分成几个小集合。那如果链表中元素比较多，查询元素的时候就又会变慢，所以当链表上元素大于一定值的时候，就会将链表转换为一颗红黑树，以此来提升查询效率，这也是源码中的做法。

避免哈希冲突

上面提到的是发生哈希冲突时的解决办法，那如尽量避免哈希冲突呢？其实哈希冲突时避免不了的，只能降低哈希冲突发生的概率。为了降低哈希冲突发生的概率可以从两个方面入手：哈希函数设计，负载因子调节

哈希函数设计

设计出更好的哈希函数显然可以更好的降低哈希冲突。

1️⃣直接定制法：取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B 优点：简单、均匀 缺点：需要事先知道关键字的分布情况 使用场景：适合查找比较小且连续的情况

2️⃣除留余数法：设散列表中允许的地址数为m**，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p<=m),**将关键码转换成哈希地址

负载因子调节

载荷因子定义：a = 插入表中的元素个数/散列表的长度

载荷因子代表哈希表的装满程度，载荷因子越大，则发生哈希冲突的概率就越高。

⭕️因此，当负载因子达到一定值的时候，就要扩容来降低负载因子，降低冲突率。提高效率。这个边界值在jdk8的HashMap源码中是0.75，也就是当负载因子达到0.75的时候，就要扩容了。

?为啥是0.75，不是别的数字0.5，1呢？这个0.75是空间和时间上的一个权衡，如果给个0.9,1，那它发送哈希冲突的概率就会变大，随之时间上效率就会变慢，但是它的空间利用率提高了。如果给个0.5，那它的冲突率低，时间效率高，但是空间利用率低。所以0.75是时间和空间上个一个权衡之后的一个值。

扩容不仅仅是增加数组长度，然后把原链表中元素直接拷贝过来或转移过来，一般来说得重新计算每个元素的哈希地址，再放入正确的位置上。

实现哈希桶

普通版本

public class HashBucket {
    static class Node{
        int key;
        int val;
        Node next;
        public Node(int key,int val){
            this.key = key;
            this.val = val;
        }
    }
    //当前桶中元素个数
    int usedSize;
    Node[] arr;
    private final double DEFAULT_VALUE = 0.75;
    //创建哈希桶
    public HashBucket(){
        arr = new Node[8];
    }

    /**
     * 存储元素
     * @param key
     * @param val
     */
    public void put(int key,int val){
        Node node = new Node(key,val);
        //计算哈希地址
        int index = key%arr.length;
        //将元素插入该index位置的链表中，这里采用头插法，实际源码中采用的是尾插法
        Node cur = arr[index];
        //遍历当前链表，判断当前链表中元素与node的key是否相同
        while(cur!=null){
            //找到key相同的元素覆盖其原val。
            if(cur.key == node.key){
                cur.val = node.val;
                return;
            }
            cur = cur.next;
        }
        //走到这里，当前链表中没有与node的key相同的元素，则把node节点头插入链表中
        cur = arr[index];
        node.next = cur;
        arr[index] = node;
        usedSize++;
        //负载因子超过限定值
        if(usedSize*1.0/arr.length >= DEFAULT_VALUE){
            //扩容
            reSize();
        }
    }

    /**
     * 扩容函数
     */
    private void reSize(){
        //创建新数组
        Node[] newArr = new Node[arr.length*2];
        //将原数组中元素移至当前新数组中
        for (int i = 0; i < arr.length; i++) {
            Node cur = arr[i];
            while(cur != null){
                Node nextNode = cur.next;
                int index = cur.key % newArr.length;
                cur.next = newArr[index];
                newArr[index] = cur;
                cur = nextNode;
            }
        }
        arr = newArr;
    }

    /**
     * 根据key获取val
     * @param key
     * @return
     */
    public int get(int key){
        for (int i = 0; i < arr.length; i++) {
            Node cur = arr[i];
            while (cur!=null){
                if (cur.key == key){
                    return cur.val;
                }
                cur = cur.next;
            }
        }
        //暂定没找到key对应的value就返回-1；
        return -1;
    }
}

泛型版本

public class HashBucket1 <K,V>{
    //定义节点
    static class Node<K,V>{
        K key;
        V val;
        Node<K,V> next;
        public Node(K key,V val){
            this.key = key;
            this.val = val;
        }
    }
    int usedSize;
    Node<K,V>[] arr;
    private static final double DEFAULT_LOAD_FACTOR = 0.75;
    //创建哈希桶
    public HashBucket1(){
        arr = (Node<K, V>[]) new Node[8];
    }
    public void put(K key,V val){
        //求得哈希值
        int hash = key.hashCode();
        int index = hash % arr.length;
        Node<K,V> cur = arr[index];
        //遍历链表，如果有key相等的元素则进行覆盖
        while (cur != null){
            if(cur.key.equals(key)){
                cur.val = val;
                return;
            }
        }
        //没有key相等的元素则进行头插
        Node<K,V> node = new Node<>(key,val);
        node.next = arr[index];
        arr[index] = node;
        usedSize++;
        //负载因子大于一定值进行扩容
        if(usedSize*1.0/arr.length >= DEFAULT_LOAD_FACTOR){
            //扩容
            reSize();
        }
    }

    //扩容函数
    private void reSize() {
        //2倍扩容
        Node<K,V>[] newArr = (Node<K, V>[])new Node[arr.length*2];
        for (int i = 0; i < arr.length; i++) {
            Node<K,V> cur = arr[i];
            while (cur !=null){
                Node<K,V> nextNode = cur.next;
                int hash = cur.key.hashCode();
                int index = hash % newArr.length;
                cur.next = newArr[index];
                newArr[index] = cur;
                cur = nextNode;
            }
        }
        arr = newArr;
    }
    public V get(K key){
        int hash = key.hashCode();
        int index = hash % arr.length;
        Node<K,V> cur = arr[index];
        while (cur != null){
            if (cur.key.equals(key)){
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }
}

?put()方法：根据key计算hash值（用到了hashCode()方法），找到应该存储的数组下标。在以当前数组下标值为头结点的链表中寻找是否有与待插入数据的key相等的元素（e1.equals(e2)返回true）。如果有需要覆盖，如果没有则插入到链表头（源码中是插入到链表尾）。

?get()方法：通过key计算hash值，然后找到下标，在当前下标的这个链表中寻找有没有key相等的元素，如果有的话返回其val，没有则返回null。

hashCode() 和equals()

?hashCode()：用来计算对象的hash值，返回的是一个int类型数字是Object类中的方法，是一个本地方法，其实是根据对象在内存中的地址转换出来的一个hash值。

Object中hashCode方法

这是生成hash值的c++代码：，也就是Object类中的hashCode()方法

static inline intptr_t get_next_hash(Thread * Self, oop obj) {
  intptr_t value = 0 ;
  if (hashCode == 0) {
     // 返回随机数
     value = os::random() ;
  } else
  if (hashCode == 1) {
     //用对象的内存地址根据某种算法进行计算
     intptr_t addrBits = cast_from_oop<intptr_t>(obj) >> 3 ;
     value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom ;
  } else
  if (hashCode == 2) {
     // 始终返回1，用于测试
     value = 1 ;            
  } else
  if (hashCode == 3) {
     //从0开始计算哈希值
     value = ++GVars.hcSequence ;
  } else
  if (hashCode == 4) {
     //输出对象的内存地址
     value = cast_from_oop<intptr_t>(obj) ;
  } else {
     // 默认的hashCode生成算法，利用xor-shift算法产生伪随机数
     unsigned t = Self->_hashStateX ;
     t ^= (t << 11) ;
     Self->_hashStateX = Self->_hashStateY ;
     Self->_hashStateY = Self->_hashStateZ ;
     Self->_hashStateZ = Self->_hashStateW ;
     unsigned v = Self->_hashStateW ;
     v = (v ^ (v >> 19)) ^ (t ^ (t >> 8)) ;
     Self->_hashStateW = v ;
     value = v ;
  }

  value &= markOopDesc::hash_mask;
  if (value == 0) value = 0xBAD ;
  assert (value != markOopDesc::no_hash, "invariant") ;
  TEVENT (hashCode: GENERATE) ;
  return value;
}

可以看出它有好几种策略来生成hash值，可以根据内存地址，也有随机数，还有固定值，或者其他算法，默认使用的是最后一种策略。不过我们在idea中可以更改策略：

在这里，比如我们设置成了0，那hash值返回的就是一个随机数。

⭕️本地c++代码生成hash值有好几种策略，具体使用哪种策略，可以设定。

重写hashCode方法

那如果我们自己定义了一个类重写了hashCode()方法，那该类的实例对象再调用hashCode()方法的时候就会调用我们重写的hashCode()方法，不会调用Object类中的那个本地方法：

import java.util.Objects;

class Student1{
    String name;

    public Student1(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student1 student1 = (Student1) o;
        return Objects.equals(name, student1.name);
    }

//    @Override
//    public int hashCode() {
//        return Objects.hash(name);
//    }
}
public class Test1 {
    public static void main(String[] args) {
        Student1 student1 = new Student1("bit");
        Student1 student2 = new Student1("bit");
        System.out.println(student1.hashCode());
        System.out.println(student2.hashCode());
    }
}

1️⃣当前我们把重写的hashCode方法注释掉了，然后再执行代码，输出的两个对象的hash值是不一样的：

2️⃣如果放开注释，调用重写的hashCode方法，则输出的hash值是一样的：

⭕️这是因为重写的hashCode是根据name属性计算得出的hash值，现在看一下重写的hashCode的源码：

先调用的是Objects类中的静态方法，然后再调用Arrays类中的hashCode方法：

Arrays类中的hashCode方法：把重写的方法中传入的参数（这个参数我们上面代码传的是name，如果属性有多个，也可以传多个，反转底层是用数组接收的，传几个参数都可以。默认generate生成的是你的类中的属性都会作为参数参与计算hash值。）作为一个Object数组，然后遍历这个数组，然后再执行：

int result = 1;
for (Object element : a)
    result = 31 * result + (element == null ? 0 : element.hashCode());

这段代码含义：将每个元素计算出的hash值+31 * result再赋值给result（如果元素是null的话，那其hash值是0）。然后每个元素的hash值是怎么计算出来的呢？每个元素当前是Object类型，则就又会调用Object类中的hashCode方法，如果你的类中的属性是int，byte，long，float，double，String这些java定义好的基本类型和引用类型则会调用其类或者包装类中的hashCode方法（因为在这些类中都实现了hashCode方法）。计算这些基本数据和引用数据的hash值，然后参与到上面代码的运算出，最终得出该对象的hash值。

既然要用基本数据类型的包装类中重写的hashCode，那么我们就去看看这些类中是如何重写的hashCode，看看他们是如何计算hash值的：

比如看一下

1️⃣String类中的hashCode：

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

?value是字符串底层对应的字符数组，它是遍历字符数组执行：h = 31 * h + val[i]，最后得出字符串的hash值。如果字符串是"a"，计算的hash值是97，如果字符串是"da"，计算的hash值是3197

2️⃣Integer类中的hashCode：

?返回的是value，也就是数字的值，2就返回2,5就返回5

3️⃣Long类中的hashCode：

?value 和 value无符号右移32位相异或，然后再强转为int类型（因为hash值都是int类型）

✅总结：

⭕️所以如果你自定义了一个类，重写了hashCode，new出了两个对象，类中属性的类型都是java定义的数据类型，且这两个对象的属性的值也是一样的，那么这两个对象hashCode计算出的hash值肯定也是一样的。

⭕️基本数据类型的包装类，以及String类都重写了HashCode方法，并且有自己的计算hash值的方法。

⭕️如果对象的属性是null，那这个属性计算出的hash值是0，在上面的Arrays类中的hashCode方法可以看出

⭕️如果重写了hashCode且重写的方法的参数里包含所有属性（也就是根据所有的属性去计算的hash值），通过这个类创建两个对象，如果两个对象的属性的值完全一样，那么这两个对象的hash值肯定是一样的，如果两个对象的hash值一样，则不能说明这两个对象的属性的值都是一样的。因为hash值是通过多个属性计算出的，就算属性不一样，可能也能凑巧得出hash值一样。

Object中equals()方法

?equals()：equals()方法是Object类中的一个方法，源码：

Object中的方法是用==比较的，所以比较的是两个对象的地址，也就是这两个对象是不是同一个对象。这是物理上的对象相等，但是在业务逻辑上，一般认为两个对象的属性一样，那这两个对象就判定为相等的。所以很多时候会重写equals方法：

重写equals()方法

class Teacher{
    int age;
    String id;

    public Teacher( String id,int age) {
        this.age = age;
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        //==判断如果返回true，说明是同一个对象，则返回true
        if (this == o) return true;
        //o是null，或者这俩对象不是同一个类的实例对象，则返回false
        if (o == null || getClass() != o.getClass()) return false;
        Teacher teacher = (Teacher) o;
        //俩对象是同一个类的实例再比较对象的属性是否都一样（这里比较的是age和id），一样返回		 //true。
        return age == teacher.age && Objects.equals(id, teacher.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, age);
    }
}

?默认生成的重写方法是根据属性是否相等来比较：具体看代码中的注释

再自动生成的equals()方法中：判断如果是同一个对象就返回true，如果不是同一个对象但是同一个类的实例对象且这俩对象的属性值都一样，也会返回true。怎么判断属性的值是否都一样呢？用这行代码判断

 return age == teacher.age && Objects.equals(id, teacher.id);

对于age是int类型，则直接==判断，对于id是String类型，引用类型，则调用Object.equals()方法来判断：

⭕️通过分析源码看出，判断id是否相等，最后还是走到了Object的euqals()方法，由于id是String类型，而在String类中重写了equals方法，所以最终判断id是否相等，会调用String类中的equals方法：

String类中的equals方法：

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = value.length;
        if (n == anotherString.value.length) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {
                if (v1[i] != v2[i])
                    return false;
                i++;
            }
            return true;
        }
    }
    return false;
}

⭕️String类中重写的equals方法是判断两个字符串的每个位置的字符是否一致，"abc"和"abc"就是一致的，“abc” 和"abd"就是不一致的。

✅总结：

⭕️Object类中的equals方法是判断两个对象是否是同一个对象，这是物理意义上的相等，一般我们自己实现的类不需要这么严谨的相等，在业务上，一般如果这俩对象的属性一样，则可以认为是相等的，所以一般会重写equasl方法。

⭕️idea自动生成的重写的equals方法判断的是属性是否相等，比如有两个属性，那默认判断两个属性是否相等。对于基本数据类型，== 就可以判断，对于引用数据类型，还是需要调用Object类中的equals方法，比如对于String类型的属性，由于String类中重写了equals方法，那最终实际调用的是String类中重写的方法。

hashCode和equals联系

1️⃣他俩都是Object类中的方法，一个是计算对象hash值，一个是判断对象是否相等。大部分时候并没啥联系

2️⃣一般重写之后，是根据对象的属性来计算对象的hash值和判断对象是否相等。

3️⃣hashCode和equals在大多数情况下，并不需要同时重写，只有在这个类的实例对象作为key添加到HashSet和HashMap等哈希表结构中时，那么这个类必须要重写hashCode和equals方法。为啥必须要同时重写hashCode和equals，在下面的源码分析中会重点剖析。

✅面试问题：两个对象的hashCode一样，equals一定一样吗？equals一样，hashCode一定一样吗？

这个问题可以加一个大前提就是：这两个对象是同一个类创建出来的，且这个类重写了hashCode()方法和equals()方法，并且重写了的hashCode和equals的方法中计算hash值的参数和判断是否相等的参数是一样的，才有讨论的意义。如果这俩方法所用的参数不一样（参数也就是对象的属性），那讨论意义不大。比如下面例子：

class Teacher{
    int age;
    String id;

    public Teacher( String id,int age) {
        this.age = age;
        this.id = id;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Teacher teacher = (Teacher) o;
        return age == teacher.age && Objects.equals(id, teacher.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, age);
    }
}

?equals中和hasCode中的参数都是用的age和id，这时候才有讨论的意义。在这种情况下，如果equals一样，那hashCode一定一样，因为equals一样，代表对象的属性（这里的属性得是java已有的数据类型，比如Integer，String。如果是自定义的类实例出的对象，而且这个自定义类没有重写hashCode可能这个属性计算出的hash值是不一样的）的值都一样，那再拿属性去计算hash值，肯定是一样的hash值。相反，如果hash值一样，属性是不一定相同的，也就是equals不一定一样，因为你属性不一样，但是计算之后也是有可能得到一样的hash值的。换个思路，hash值是一个int类型的整数，是有一定范围的。当不同属性的对象足够多，那肯定会出现一样的hash值的。

HashMap源码分析

再分析源码前，先抛出一个问题：

HashMap<String,Integer> hashMap = new HashMap<>();
HashMap<String,Integer> hashMap1 = new HashMap<>(19);

这两个哈希桶的初识容量是多少？

带着这个问题我们去分析源码：

1️⃣HashMap的成员变量：

哈希桶：

2️⃣节点对应的内部类：

3️⃣调用不带参数的构造方法：

?总共调用了两个方法，给loadFactor这个成员变量设置了0.75这个负载因子边界。并没有创建数组，所以此时数组的大小为0。那数组大小为0，怎么put元素呢？其实开辟数组空间是在put方法中实现的。

4️⃣调用put方法：

在hash方法中会根据key计算hash值，不过它并不是直接返回的key.hashCode()，而是将hash值与hash值无符号右移16位的异或值返回了。（这样做是为了让计算出的下标更均匀的分布在哈希表中）（如果key是null则直接返回0）

5️⃣调用putVal方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        //table当前为null，会调用扩容函数resize()
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

6️⃣当第一次调用putVal()时，由于table为null，所以会调用resize()方法：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    //第一次调用当前方法不会走这个if语句
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

第一次调用resize()方法，oldTab为null，oldCap被赋值为0。oldThr也是0，然后执行下面代码：

else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

newCap被赋值为DEFAULT_INITIAL_CAPACITY，也就是16，然后真正创建数组，把数组赋值给table，走到这里table才真正指向一个数组，数组的大小是16，然后resize方法返回newTab。

Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

到这里当我们调用无参的构造方法，创建HashMap的时候的哈希桶的大小就知道了，是0。当第一次put()的时候才会真正创建出数组，数组的长度是16。还有一个问题，如果创建的时候给了初识化的容量19，那数组是多大，这个在下面解决

⭕️然后resize执行结束，返回值是新创建的数组，再接着执行putVal方法：

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

i = (n - 1) & hash是计算下标，如果数组下标处的值是null，就直接创建一个节点，放入到该下标处。下面来看计算下标：

n是当前数组的长度，hash是通过调用hash函数计算出的hash值。HashMap的源码中规定了数组的长度必须是2的n次幂，有了这个约定，那(n - 1) & hash 和 hash%n的值是一样的。所以两个方法定位的是同一个下标。

如果当前下标不为null，那就说明发生哈希冲突了，需要插入到当前链表尾或者红黑树中，走下面的代码：

else {
    Node<K,V> e; K k;
    //p是当前链表的头节点，如果头节点的hash和待插入元素的hash一样，而且这俩元素的key一样，那么e指向头节点
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    //如果p是树节点，则把节点插入到红黑树
    else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
        //遍历链表，把节点插入到链表尾
        for (int binCount = 0; ; ++binCount) {
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);
                //树化的第一个条件，链表有8个元素
                if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    treeifyBin(tab, hash);
                break;
            }
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;
            p = e;
        }
    }
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
}

在遍历链表的过程中，如果当前链表够8个元素了，则调用treeifyBin(tab, hash)：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果数组的长度不够MIN_TREEIFY_CAPACITY（64），则调用的是扩容函数，并不进行树化
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

?走到这个函数中发现树化还有一个条件：数组的长度>=64。所以树化有两个条件：链表长度>=8以及数组长度>=64。只满足链表长度>=8这一个条件会调用扩容函数，不会进行树化。

此时，还有一个问题，如果创建HashMap对象的时候，给定了初识容量19，那底层的数组大小是多少？

通过深究调用关系，发现最后tableSizeFor(int cap)方法返回的是>=19的一个最下的2的n次幂。也就是会返回32。那threshold就会被赋值32，然后当第一次调用put()函数，再调用resize方法，在resize方法中会根据threshold作为要创建的数组的长度，那最终创建出的数组的长度就是32。

✅总结一下：

1️⃣树化条件：链表长度 >= 8 && 数组的长度>=64。仅仅链表长度够了，数组长度不够，调用的是扩容函数，并不会进行树化。

2️⃣创建HashMap对象时，不管给不给初识容量，都不会创建数组，当第一次调用put方法才会调用resize方法创建数组，如果创建对象时没有指定初识容量，那创建出的数组大小是16，如果给了指定容量，那么创建出的数组大小是>=给定容量的最小的2^n。

3️⃣确定元素要存放的下标时，先让key调用hashCode方法，计算hash值，然后hash值按位异或上hash值无符号右移16位，得到一个用于确定下标的hash值，然后(n - 1) & hash（n是数组长度），计算出下标。确定出要存放的桶。如果该桶下没有元素，则把该元素放入当前下标处，如果有元素的话，则在当前链表中寻找有没有和待插入元素的key一样的元素，判断key是否相等用的是equals方法。如果有则覆盖，如果没有则插入到链表尾。

?在向HashMap中插入元素的时候，需要先hashCode计算元素的key的hash值，然后再根据hash值转换为下标，确定是哪个位置，在当前位置的链表中用equals判断有没有和待插入元素的key相等的元素。所以hashCode()定位的是元素要插入到哪个下标的链表中，equals比较的是元素的key是否相等。

hashCode和equals重写问题

✅面试问题：啥时候要重写hashCode和equals，这俩需要同时重写吗，只重写一个行吗？

?如果自定义类的对象没有作为HashMap或者HashSet（这些底层是哈希表的集合类）的key，那么这俩方法是没有关联的，如果你的类中需要重写equals那就重写equals，如果需要重写hashCode，那就重写hashCode，并不是俩方法重写了其中一个，另一个也得重写。

?如果自定义类的对象作为HashMap或者HashSet（这些底层是哈希表的集合类）的key，那么这俩方法必须都要重写。如果只重写equals，没有重写hashCode。因为如果没有重写HashMap，那底层计算hash值用的是Object类中的hashCode方法。这样就会导致一个问题，就是重写了equasl（并且是根据属性值判断相等），那么在业务上，一般认为如果两个对象的属性值都一样，那么这里对象就相等。但是比如下面这个例子，创建了两个对象作为key，其属性值都一样，但是因为用的Object中的hashCode计算的hash值，那这俩 对象的hash值不一样，则入哈希桶的时候大概率入的是不同下标，那么在源码中就会出现key一样，但是并没有覆盖这种情况。那这时就在哈希桶中存在两个key一样的元素，这是不行的，Map中的key不能重复，如果这时候再创建第三个对象（其属性值和前两个都一样）作为key，调用get方法，那大概率是找不到value的（那就会返回null），因为第三个对象的hash值又不一样了。所以不重写hashCode不符合业务逻辑。

Teacher类中没有重写hashCode方法：

同理只重写hashCode，不重写equasl也是不行的，只重写hashCode，假如还是上面的代码那么sutdent1和student2会入到同一个链表中，因为其hash值计算结果相同，但是不会覆盖，因为用的Object中的equals方法，这俩对象的地址不一样，所以equasl返回false，这样俩对象就都存到同一个链表中了。后期执行System.out.println(hashMap.get(teacher3));还是返回null，必须得用物理地址相同的对象才能取出其value值。这一般也是不符合业务逻辑的。

?所以最终得出的结论是如果对象作为key存储到底层是哈希表的集合类中，那么对象的类必须重写hashCode和equals。

?==另外如果两个对象的equals相等，那么其hashCode必须得相等。==且对象是作为key存储到哈希表结构中的，那么既然两个对象的equals相等，那得存储到一个链表中，如果hash值不等，那大概率是存储不到一个链表中，那就没法覆盖，那在Map中就会出现两个一样的key。所以得保证equals相等，hashCode也必须得相等。那所以重写的equals方法中用的什么属性去判断的，在hashCode中也得用一样的属性去判断。也就是equals用的是对象的name和Id属性去判断的，hashCode也得用name和Id属性去计算hash值。