浅谈HashMap

一、什么是hash算法

哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。

在java中，任意对象都有一个hash值，就是通过hash算法得出。

---

 二、一个对象默认用什么作为hashcode 

Object中定义的hashCode方法为不同对象返回不同的整数，未重写hashCode方法时一般通过将对象的内部地址转换为整数来实现，重写后一般通过将对象的内容转换为整数来实现。

---

三、为什么修改equals方法时，还需重写hashcode方法

1、只要在执行Java应用程序时多次在同一个对象上调用该方法， hashCode方法必须始终返回相同的整数。

2、如果根据equals(Object)方法两个对象相等，则在两个对象中的每个对象上调用hashCode方法必须产生相同的整数结果。

---

四、HashMap怎样判断为同一对象 

 通过对象本身的equals方法来判断是同一对象。

---

五、一个对象放到HashMap中的过程         1、获得key对象的hashcode

                 首先调用key对象的hashcode()方法，获得hashcode。

        2、将hashcode再次hash

                hashcode是一个整数，我们需要将它转化成[0,数组长度-1]区间）的范围。我们要求转化 后的hash值尽量均匀地分布在[0,数组长度-1]区间）,减少“hash冲突”。 

  一个简单和常用的计算hash值的算法（相除取余算法）

•    hash值=hashcode%数组的长度

这种算法可以让hash值均匀的分布在[0,数组长度-1]的区间。

早期HashTable就是采用这种算法。但是，这种算法由于使用了“除法”，效率低下。JDK后来改进了算法。首先约定数组长度必须为2的整数幂，这样采用位运算即可实现取余的效果：

• hash值=hashcode&(数组长度-1)。

        测试Hash算法 

public class hashTest {
//测试hash算法
    public static void main(String[] args) {
     int h=25860399;
     int length=16;//length为2的整数次幂，则h&（length-1）相当于length取模
        myHash(h,length);
 
    }
    public static int myHash(int h,int length){
        System.out.println("通过位运算实现取余操作:"+(h&(length-1)));
        System.out.println("直接取余操作:"+(h%length));
        return h&(length-1);
    }
}

         3、生成Entry对象

                一个Entry对象包含4部分：key对象、value对象、hash值、指向下一个Entry对象的引用。我们现在算出了hash值。下一个Entry对象的引用为null。 

         4、将Entry对象放入数组

        如果本Entry对象对应的数组索引位置还没有放Entry对象，则直接将Entry对象存储进数组；如果对应索引位置已经有Entry对象，则将已有Entry对象的next指向本Entry对象，形成链表。 

---

总结：

        当添加一个元素（key-value）时，首先计算key的hashcode的hash值（两次hash），以此确定插入数组中的位置，但是可能存在同一个hash值的元素已经放在同一位置了，这是就添加到同一hash值元素的后面，他们在数组同一个位置，就形成了链表，同一个链表上的hash值是相同的，所以说数组存放的是链表。 

---

六、HashMap和HashSet的数据结构 

 HashMap的数据结构采用的哈希表，即数组+链表。

 HashSet基于HashMap实现的，HashSet 底层使用HashMap   来保存所有元素，将     HashSet 的数据作为HashMap的Key值保存。

---

七、什么叫做哈希碰撞 

当不同的对象拥有相同的哈希值，就是两个key定位到了相同的位置，就叫做哈希碰撞。

这些对象在哈希表中存放在同一个链表之中，我们应该极力避免这种情况，让他的哈希值尽可能的散列开来，以获得更好的性能。

---

八、怎样优化HashMap 

有时两个key会定位到相同的位置，表示发生了Hash碰撞。如果使Hash算法计算结果越分散均匀，Hash碰撞的概率就越小，map的存取效率就会越高。

---

九、什么是HashMap的扩展因子，为什么是0.75 

HashMap的扩展因子是指，当HashMap的数组达到容量的多少时，会进行扩容。

HashMap的位桶数组，初始大小为16，实际使用时，显然大小是可变的。如果位桶数组中的元素达到（0.75*数组length）,就重新调整数组大小变为原来2倍大小。

---

        扩容很耗时的，扩容的本质是定义新的更大的数组，并将旧的数组内容挨个拷贝到新的数组中，如果将扩容因子定义的太小，就需要频繁的创建新的数组将旧数组的数据移过去，非常消耗性能。

        而如果扩容因子越大，哈希碰撞的概率也就越大，即可能造成同一链表上的数据变得很多，每当查找时每次都需要遍历一次，花费的时间很多，导致效率也会大打折扣。
        因此扩容因子=0.75也是空间和时间平衡考虑之后的结果。