哈希表的详细和其实现~

哈希冲突：不同的关键字通过相同的哈希函数，有可能找到相同的位置

如何避免冲突：（冲突的发生是必然的，但我们能做的应该是尽量的降低冲突率）

1、设计哈希函数来比避免冲突

（1）哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1 之间，就是散列表有多少格子就用多少格子的意思

（2）哈希函数计算出来的地址能均匀分布在整个空间中

1. 直接定制法 --(常用 )

取关键字的某个线性函数为散列地址： Hash （ Key ） = A*Key B 优点：简单、均匀

缺点：需要 事先知道关键字的分布情况         使用场景： 适合查找比较小且连续的情况

 面试题：字符串中第一个只出现一次字符

思路：因为知道了字符串中都是小写字母，就是 事先知道关键字的分布情况 

           小写字母还是连续的并且范围较小，所以可以用哈希的方法

1.  
   public int firstUnique(String s){
2.  
   if(s==null){
3.  
   return -1;
4.  
   }
5.  
   int[] array=new int[26];
6.  
   for (int i = 0; i < s.length(); i ) {//第一次遍历str，把里面的元素都放入array里
7.  
   char ch=s.charAt(i);
8.  
   array[ch-97] ;
9.  
   }
10.  
    for (int i = 0; i <s.length() ; i ) {//第二次遍历str，每遍历一个元素上array里检查一下，若为1，则返回
11.  
    char ch=s.charAt(i);
12.  
    if(array[ch-97]==1){
13.  
    return i;
14.  
    }
15.  
    }
16.  
    return -1;
17.  
    }

2. 除留余数法--(常用)

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

负载因子=存储散列表元素的个数/散列表的长度（负载因子=0.75，一旦大于0.75需要调节）

负载因子和冲突的关系：

 可知：负载因子越小，冲突率越低

要想降低冲突，需要将负载因子降低，由于存储散列表元素的个数在慢慢增加，所以要想负载因子降低只能提高散列表的长度，因此要想降低冲突，需要提高散列表的长度

由于冲突是避免不了的，那真正发生冲突又该怎么解决呢？

1、闭散列（开放地址法）：就是去寻找下一个为空的位置

   （1）线性探测：从冲突的位置开始向后找找到第一个为空的位置将元素放进去

缺点：会把冲突的元素都放到一起了，这样就不能随便删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索。比如删除元素4，如果直接删除掉，44查找起来可能会受影响。因此线性探测采用标记的伪删除法来删除一个元素。

 （2）二次探测：

 缺点：空间利用率较低，只能装一半的元素，如果超出必须考虑增容。

2、（重点）开散列（哈希桶HashBuck/链地址法/开链法）

底层就是：数组（数组里面存的是Node） 链表

有人会担心，链表长度万一很长，遍历的时候时间复杂度不就会变成O（N）嘛？ 

这点请放心，因为链表的长度不会很长，控制在常数范围内，因为需要控制负载因子。

从JDK1.8开始，当链表长度超过8，并且数组的长度超过64时，这个链表就会变成红黑树

红黑树查找非常高效，不用担心时间复杂度问题。

通常认为哈希表的插入/删除/查找时间复杂度是 O(1)

 1、简单实现哈希表~

1.  
   public class HashBuck {
2.  
   static class Node{
3.  
   public int key;
4.  
   public int val;
5.  
   public Node next;
6.  
   public Node(int key,int val){
7.  
   this.key=key;
8.  
   this.val=val;
9.  
   }
10.  
    }
11.  
    public Node[] array;
12.  
    public int usedSize;
13.  
     
14.  
    public static final double DEFAULT_LOAD_FACTOR=0.75;//规定负载因子，添加数据时检查一下，防止冲突
15.  
     
16.  
    public HashBuck(){
17.  
    this.array=new Node[10];
18.  
    }
19.  
    //添加元素
20.  
    public void put(int key,int val){
21.  
    //1、找到key所对应在array中的位置
22.  
    int index=key% array.length;
23.  
    //2、遍历index位置的链表，看key是否重复，重复则替换，若key不在则插入链表中
24.  
    //2.1重复的时候
25.  
    Node cur=array[index];
26.  
    while(cur!=null){
27.  
    if(cur.key==key){
28.  
    cur.val=val;//key重复，替换val
29.  
    return;
30.  
    }
31.  
    cur=cur.next;
32.  
    }
33.  
    //2.2不重复的时候：头插法插入
34.  
    Node node=new Node(key, val);
35.  
    node.next=array[index];//绑定尾部
36.  
    array[index]=node;//绑定头部
37.  
    usedSize ;
38.  
    //3、检查负载因子，超出负载因子的值，则需要扩大array的容量来减小负载因子的值，防止冲突
39.  
    if(loadFactor()>=DEFAULT_LOAD_FACTOR){
40.  
    resize();//扩容array的方法
41.  
    }
42.  
    }
43.  
    //扩容array需要注意：此时由于array扩容变长 需要将原来没扩容之前的节点都拿出来，
44.  
    // 然后重新哈希每个节点找在扩容后数组中的位置
45.  
    private void resize(){
46.  
    Node[]newArray=new Node[2*array.length];
47.  
    for (int i = 0; i < array.length; i ) {//遍历原来的数组，将里面的节点全都拿出来
48.  
    Node cur=array[i];//拿里面的节点
49.  
    while(cur!=null){//有可能array里的每个位置里都不止一个节点，而是一个链表
50.  
    int index=cur.key%newArray.length;//找到节点在扩容后数组中的位置
51.  
    Node curNext=cur.next;
52.  
    cur.next=newArray[index];//绑定后面
53.  
    newArray[index]=cur;//绑定前面
54.  
    cur=curNext;
55.  
    }
56.  
    }
57.  
    array=newArray;//让扩容后的数组代替原来的数组
58.  
    }
59.  
     
60.  
    private double loadFactor(){//求当前的负载因子值
61.  
    return 1.0*usedSize/array.length;//负载因子=当前数据长度/数组长度
62.  
    }
63.  
     
64.  
    //根据key获取val值
65.  
    public int get(int key){
66.  
    //1、找key的位置（大概找到key所在array数组的哪个下标里）
67.  
    int index=key%array.length;
68.  
    //2、遍历这个下标的链表具体找到key
69.  
    Node cur=array[index];
70.  
    while(cur!=null){
71.  
    if(cur.key==key){
72.  
    return cur.val;
73.  
    }
74.  
    cur=cur.next;
75.  
    }
76.  
    return -1;
77.  
    }
78.  
     
79.  
    public static void main(String[] args) {
80.  
    HashBuck hashBuck=new HashBuck();
81.  
    hashBuck.put(1,1);
82.  
    hashBuck.put(2,2);
83.  
    hashBuck.put(4,4);
84.  
    hashBuck.put(6,6);
85.  
    hashBuck.put(13,13);
86.  
    hashBuck.put(12,12);
87.  
    hashBuck.put(11,11);
88.  
    hashBuck.put(8,8);
89.  
    System.out.println(hashBuck.get(11));
90.  
    }
91.  
    }

关于hashCode函数：可以使一个引用变成一个合法的整数

1.  
   //假设接下来的key是一个person，身份证号是一样的，我们认为是同一个人
2.  
   //又因为，要把person1和person2放到散列表中，需要找到index，所以需要调用person.hashcode(),找到下标
3.  
   class Person{
4.  
   public String ID;
5.  
   public Person(String ID){
6.  
   this.ID=ID;
7.  
   }
8.  
   @Override
9.  
   public String toString() {
10.  
    return "Person{"
11.  
    "ID='" ID '\''
12.  
    '}';
13.  
    }
14.  
    }
15.  
    public static void main(String[] args) {
16.  
    Person person1=new Person("123");
17.  
    Person person2=new Person("123");
18.  
    System.out.println(person1.hashCode());
19.  
    System.out.println(person2.hashCode());
20.  
    }

 因为是同一个人，所以需要生成的值是一样的，这样才能存到同一位置，可是按照上面显然是不能达到预期的，因此还需要加东西，让生成的hashCode值相同

1.  
   class Person{
2.  
   public String ID;
3.  
   public Person(String ID){
4.  
   this.ID=ID;
5.  
   }
6.  
   @Override
7.  
   public boolean equals(Object o) {
8.  
   if (this == o) return true;
9.  
   if (o == null || getClass() != o.getClass()) return false;
10.  
    Person person = (Person) o;
11.  
    return Objects.equals(ID, person.ID);
12.  
    }
13.  
    @Override
14.  
    public int hashCode() {
15.  
    return Objects.hash(ID);
16.  
    }
17.  
    @Override
18.  
    public String toString() {
19.  
    return "Person{"
20.  
    "ID='" ID '\''
21.  
    '}';
22.  
    }
23.  
    }
24.  
     
25.  
    public class HashBuck2 {
26.  
    public static void main(String[] args) {
27.  
    Person person1=new Person("123");
28.  
    Person person2=new Person("123");
29.  
    System.out.println(person1.hashCode());
30.  
    System.out.println(person2.hashCode());
31.  
    }
32.  
    }

 重写了hashCode和equals后发现生成的值相等了，满足了预期

总结：因为HashMap底层是一个哈希表，所以在使用HashMap时如果map里面存的key值是自定义类型，一定要重写HashCode

像这种情况就要重写。 否则就会出现本意是一个人的两个人，最终被误认为不是一个人，被放到了不同位置

2、改进实现哈希表

1.  
   import java.util.Objects;
2.  
   //改进哈希表（由于哈希表里面的值不一定是整数）
3.  
   class Person{
4.  
   public String ID;
5.  
   public Person(String ID){
6.  
   this.ID=ID;
7.  
   }
8.  
    
9.  
   @Override
10.  
    public String toString() {
11.  
    return "Person{"
12.  
    "ID='" ID '\''
13.  
    '}';
14.  
    }
15.  
    //如果哈希表里存的树自定义对象时，在进行插入和查找时要重写equals（）和hashCode（）两个方法
16.  
    @Override
17.  
    public boolean equals(Object o) {
18.  
    if (this == o) return true;
19.  
    if (o == null || getClass() != o.getClass()) return false;
20.  
    Person person = (Person) o;
21.  
    return Objects.equals(ID, person.ID);
22.  
    }
23.  
     
24.  
    @Override
25.  
    public int hashCode() {
26.  
    return Objects.hash(ID);
27.  
    }
28.  
    }
29.  
    public class HashBuck2 <K,V>{
30.  
    static class Node<K,V>{
31.  
    public K key;
32.  
    public V val;
33.  
    public Node<K,V> next;
34.  
    public Node(K key,V val){
35.  
    this.key=key;
36.  
    this.val=val;
37.  
    }
38.  
    }
39.  
     
40.  
    public Node<K,V>[] array=(Node<K,V>[])new Node[10];
41.  
    public int usedSize;
42.  
    public void put(K key,V val){
43.  
    int hash=key.hashCode();//通过hashCode（）来将一个字符串转换成对应值，
44.  
    // 进而通过生成的值来找其在array数组中的位置
45.  
    int index=hash%array.length;
46.  
    Node<K,V> cur=array[index];
47.  
    while(cur!=null){
48.  
    if(cur.key.equals(key)){
49.  
    cur.val=val;
50.  
    return;//此时相同的值再次插入，替换完val值后return
51.  
    }
52.  
    cur=cur.next;
53.  
    }
54.  
    Node<K,V> node=new Node<>(key,val);
55.  
    node.next=array[index];
56.  
    array[index]=node;
57.  
    this.usedSize ;
58.  
    }
59.  
    public V get(K key){
60.  
    int hash=key.hashCode();
61.  
    int index=hash%array.length;
62.  
    Node<K,V> cur=array[index];
63.  
    while(cur!=null){
64.  
    if(cur.key.equals(key)){
65.  
    return cur.val;
66.  
    }
67.  
    cur=cur.next;
68.  
    }
69.  
    return null;
70.  
    }
71.  
     
72.  
    public static void main(String[] args) {
73.  
    Person person1=new Person("123");
74.  
    Person person2=new Person("123");
75.  
    HashBuck2<Person,String> hashBuck2=new HashBuck2<>();
76.  
    hashBuck2.put(person1,"ly");
77.  
    System.out.println(hashBuck2.get(person2));
78.  
    }
79.  
     
80.  
    public static void main1(String[] args) {
81.  
    Person person1=new Person("123");
82.  
    Person person2=new Person("123");
83.  
    System.out.println(person1.hashCode());
84.  
    System.out.println(person2.hashCode());
85.  
    }
86.  
     
87.  
     
88.  
    }

总结：

1. HashMap 和 HashSet 即 java 中利用哈希表实现的 Map 和 Set

2. java 中使用的是哈希桶方式解决冲突的

3. java 会在冲突链表长度大于一定阈值后，将链表转变为搜索树（红黑树）

4. java 中 计算哈希值 实际上是 调用的类的 hashCode 方法 ， 进行 key 的相等性比较 是调用 key 的 equals方 法 。

所以 如果要用自定义类作为 HashMap 的 key 或者 HashSet 的值，必须覆写 hashCode 和 equals 方法 ，而且要做到 equals 相等的对象， hashCode 一定是一致的

这篇好文章是转载于：学新通技术网