集合-HashMap（对象数组+链表）及Map下的其他集合

构造方法

注意：散列因子默认为0.75，初始桶的数量为16，每次扩容变为原来的2倍。JDK1.8，哈希桶中数据大于8时，从链表变为红黑树，数据减小到6时，从红黑树转为链表（之前转为红黑树过）。

put方法

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    //根据Key算出哈希值
static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //判断是否为0或为空
        if ((tab = table) == null || (n = tab.length) == 0)
            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;
            //如果发现重复e就会被赋值
            //发现第一个和要存的键值一样
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
                //判断一下现在是不是红黑树结构
            else if (p instanceof TreeNode)
            //如果存储的时候发生覆盖，e会被赋值
                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;
                    }
                    //重复，给e赋值
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //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;
    }

使用

put:

HashMap<String,String> map = new HashMap<>();
        map.put("何世鹏","2020");

get:

//根据建值取数据
        String test = map.get("key1");
        System.out.println(test);

遍历：
1.通过keySet获得键值，然后通过get方法获得值

Set<String> set = map.keySet();
        for (String s:set) {
            System.out.println(map.get(s));
        }

2.通过values遍历

Collection<String> values = map.values();
        for (String s:values) {
            System.out.println(s);
        }

Map接口下其他接口使用方法类似

例如：HashMap、Hashtable、ConcurrentHashMap、TreeMap、LinkedHashMap
注意：TreeMap使用自定义类时，需要实现Comparable接口下的CompareTo方法。

区别

线程安全与否
HashMap：线程不安全，效率高
Hashtable：线程安全，效率低
ConcurrentHashMap：采用分段锁机制，保证线程安全，效率又比较高
存储顺序
TreeMap：系统规定的顺序
LinkedHashMap：传入顺序
HashMap：不保证顺序

散列表散列操作

散列：重新创建一个内部数据结构，如果初始哈希桶数量不合理可能会出现存储1万个数据，存储次数为3-4万。
散列因子：初始值为0.75，表示如果又75%的哈希桶被使用了，就发生散列。
初始容量：哈希桶的数量。

注意：尽可能避免散列，提高效率。散列因子越大利用率越好，效率越低，0.75是官方测试后效果最好的数值。

存储自定义对象

package HashMap;

import java.util.*;

public class HashMapTest {
    public static void main(String[] args) {
        HashMap<Book,String> map = new HashMap<>();
        Book book1 = new Book("金苹果","讲述了果农辛勤种植的艰辛路程");
        map.put(book1,"我们人生的第一本书！");
        Book book2 = new Book("银苹果","讲述了果农辛勤种植的艰辛路程（银）");
        map.put(book2,"我们人生的第二本书");

        String test = map.get(book1);
        System.out.println(book1);


    }
}

class Book{
    String name;
    String info;

    public Book() {
    }

    public Book(String name, String info) {
        this.name = name;
        this.info = info;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getInfo() {
        return info;
    }

    public void setInfo(String info) {
        this.info = info;
    }

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

    @Override
    public int hashCode() {
        return Objects.hash(name, info);
    }

    @Override
    public String toString() {
        return "Book{" +
                "name='" + name + '\'' +
                ", info='" + info + '\'' +
                '}';
    }
}

注意：
1.需要在类中重写hashCode方法，否则会使用Objects里的Hashcode方法，效率会下降。
2.作为键值存入时，hashCode方法根据name和info计算哈希值，存入Map后不能对计算要用到的值进行更改，否则可能查询不到数据。（键值存入后不要改动，非键值可以）

public int hashCode() {
        return Objects.hash(name, info);
    }

HashMap的所有方法