HashMap的原理:

数组+链表+红黑树。

用hash(值)计算所在数组的下标，hash(值)能够一次定位到数组下标，所以在不考虑哈希冲突的情况下, 查找、删除、插入操作的时间复杂度是O(1)。但在发生哈希冲突时，仍然要遍历整个链表，时间复杂度为O(n)，所以链表越少性能越好。

当hash(值1)、hash(值2)得到的结果相同时,就称发生了哈希冲突。发生哈希冲突后，值1和值2要放在那里呢？hashMap采用了链地址法，也就是数组+链表的方式。当hash(值1)、hash(值2)得到数组的同一个下标时，就在当前下标位置生成一个二叉树，把这两个值都放里面。

HashMap源码

数据结构

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化容量 // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;     //默认负载因子大小
static final int TREEIFY_THRESHOLD = 8;             //变树临界值
static final int MIN_TREEIFY_CAPACITY = 64;          //最小树容量？

transient int size;     //map中实际包含的数据的个数
transient int modCount;

node: hash、key、value、next

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

TreeNode: parent、left、right、prev、red

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }

初始化

使用构造函数进行初始化，规定了初始容量和负载因子。

initialCapacity – the initial capacity 初始容量，默认为16。

　　如果指定初始容量的话，会在内部转化为大于初始值的2的N次方。tableSizeFor
loadFactor – the load factor 负载因子,默认为0.75

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity); //tableSizeFor函数返回给定值容量的2次幂
}

put

数组下标：(数组长度 - 1) & hash

//外部调用
//计算key的hash值后，调用内部的putVal()插入数据。
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
    //hash(key)为(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; //table
    Node<K,V> p;//数组上的节点。
    int n, i;
    //如果table没有被初始化，或者table的长度为0，则用resize()初始化。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    //计算该值对应的数组下标Index的位置有没有值
    if ((p = tab[i = (n - 1) & hash]) == null)
        //如果没有值，得到null则新建一个节点，赋值到对应index上。（没有发生哈希冲入时，进行插入操作的情况）
        tab[i] = newNode(hash, key, value, null);
    else {
       //如果有值。即发生hash冲突时，怎么进行插入操作。
        Node<K,V> e; 
        K k;
       //如果节点存在在数组上，key值相等，则直接覆盖。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)//如果这个值不是在数组节点上，那应该是在这个数组节点的链表上。可能是在Node上，可能是在TreeNode上。
            //如果节点类型为TreeNode，这个k-v值在红黑数上。则进行红黑树的插入
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            //如果节点类型不为TreeNode，是Node，这个k-v值不在红黑树，在链表上。则遍历链表,跟在第一个节点的next不为null的节点后.
            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;
}


怎么变树？
怎么进行红黑二叉树插入?

get

判断第一个节点是不是红黑树，如果是红黑树，就按树取。如果是链表就按链表取。

扩容

https://blog.csdn.net/u010890358/article/details/80496144

HashMap有序吗？

HashMap不保证插入顺序，但是循环遍历时，输出顺序是不会改变的。外层循环遍历数组，内层循环遍历单链表。

但元素的在数组中的下标的计算公式是：(n-1) & hash,n代表初始容量，如果初始容量不一样，那么元素所在下标也不一样。若两个Map的初始化容量不一致，就算插入相同的key，最后输出顺序也不一定一样。

TreeHash

TreeMap和HashMap继承了AbstractMap。

TreeMap可以对元素进行排序，由Comparator或Comparable确定

LinkedhashMap

LinkedHashMap继承于HashMap，在其基础上，内部又增加了一个链表，用于存放元素的顺序。基于元素增加或访问的先后顺序进行排序。

JAVA的其他数据结构：

数据结构是指计算机底层存储、组织数据的方式。合适的数据结构可以带来更高的存储或运行的效率。

Java中的数据结构有：数组、链表、二叉树、哈希表等。不同结构的插入、删除、查找的时间复杂度不一样。

	插入	删除	查找
数组	O(n)	O(n)	下标查找：O(1) 数值查找：无序 O(n) 有序：二分查找、插值查找、斐波那契查找O(log n)
链表	O(1)	O(1)	O(1)
二叉树	O(log n)	O(log n)	O(log n)
哈希表	O(1)	O(1)	不考虑哈希冲突的前提下：O(1)

而数据结构的底层物理存储结构只有两种：顺序存储结构和链式存储结构。