HashMap的实现原理(简要概述)

HashMap的实现原理(简要概述)

基于哈希算法实现的,它通过put存储,通过get取值.
当传入一个key时,HashMap会根据()计算出哈希值,然后根据这个哈希值将value保存到哈希桶中.

 原理分析:

从结构上来说,HashMap是由数组+链表+红黑树实现的,（最初主要是通过数组存储，链表是为了解决哈希冲突，但是在哈希碰撞次数大于一定的量时，就需要引用红黑树来处理了）源码写在下面

---

 static class Node<K,V> implements <K,V> {
		//定义数组索引的位置
		final int hash;
		//K,V
		final K key;
		V value;
		//定义下一个链表的节点
		Node<K,V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
         = hash;
         = key;
         = value;
         = next;
    }
	//获取K,V 的值
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
	//获取hashCode值
    public final int hashCode() {
        return (key) ^ (value);
    }
	//设置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 ) {
            <?,?> e = (<?,?>)o;
            if ((key, ()) &&
                (value, ()))
                return true;
        }
        return false;
    }
}
--------------------------------------------------------

HashMap是使用哈希表来存储的，为了解决哈希冲突，我们通常采用链地址法，简而言之就是说采用数组加链表的结合，每一个数组元素上都有一个链表结构。通过get获取到数据时，可以获取到数组的下表，然后把数据（value）放到对应下表的链表上。 系统调用这个key的hashCode方法得到hashCode值，然后通过高位和取模运算来定位键值对的存储位置。但是当发生两个key定位到相同位置的时候，就发生了哈希冲突。

 哈希冲突？

哈希表存储数据是通过键值对（key-value）的方式存储的，一个key对应一个value，但是也可能发生特殊情况，可能两个不同的key值在经过哈希运算后得到同样的结果，这样就是哈希冲突（碰撞）。

关于哈希表的初始化长度

哈希表的初始化长度length=16 , 负载因子(LoadFactor)默认值=0.75
threshod = length * LoadFactor (阈值=初始长度*负载因子)
阈值就是允许的最大元素数目,超过这个数目就会重新扩容