9.哈希表

9.哈希表
强烈推介IDEA2020.2破解激活,IntelliJ IDEA 注册码,2020.2 IDEA 激活码

目录

1.哈希表的基本介绍
2.哈希表的设计思想
3.哈希函数的设计
4.哈希表大小的确定
5.冲突的解决
6.哈希表的实现
7.哈希表总结

1.哈希表的基本介绍

散列表(Hash table,也叫哈希表),是根据关键字(Key value)而直接访问在内存存储位置的数据结构。也就是说,它通过一个计算键值的函数,将所需查询的数据映射到表中一个位置来方便访问,这加快了查找速度。这个映射函数称做散列函数,又叫哈希函数,存放数据的数组称做散列表(哈希表)。因此它同数组、链表以及二叉排序树等相比较有很明显的区别,它能够快速定位到想要查找的记录,而不是与表中存在的关键字进行依次比较来进行查找。

2.哈希表的设计思想

举例说明哈希表同其他数据结构的区别:

对于一般的线性表,比如链表,如果要存储学生信息:姓名、学号。在JAVA中一般就是将姓名和年龄这些信息作为"学生类"的成员变量,然后把这些学生对象存放到链表中,当要查找如"张三 1001"这条记录时,需要从链表头节点开始遍历,并依次将每个结点中的姓名同"张三 "比较,直到查找成功或失败,这种做法的时间复杂度为O(n)。即使采用二叉排序树进行存储,也最多为O(logn)。假设能够通过"张三"这个信息直接获取到该记录在表中的存储位置,就能省掉中间关键字比较的环节,复杂度直接降到O(1)。这便是哈希表能够实现的。

详解哈希表的设计思想:

Hash表通过上述提到的映射函数(哈希函数),记为hashFunc(key),直接将关键字key(待插入或查找的数据)映射到表中的一个存储位置上,从而在想要查找该数据时,可以直接根据关键字和映射关系计算出该数据在表中的存储位置。通过Hash函数f和关键字计算出来的存储位置(注意这里的存储位置只是表中的存储位置,并不是实际的物理地址)称作为Hash地址。比如上述例子中,假如学生信息采用Hash表存储,则当想要找到"张三"的信息时,直接将"张三"作为Hash函数f的参数:hashFunc(“张三”),计算出Hash地址即可。

3.哈希函数的设计

上述提到的哈希函数hashFunc(key)并不是一个固定的规则,而是我们根据实际需求自己设计的。Hash函数设计的好坏直接影响到对Hash表的操作效率。那如何设计哈希函数或者哈希函数的设计有哪些需要注意的呢?

假如对上述的学生信息进行存储时,采用的Hash函数为 姓名的每个字的拼音开头大写字母的ASCII码之和
hashFunc(张三)=ASCII(Z)+ASCII(S)=90+83=173;
hashFunc(李四)=ASCII(L)+ASCII(S)=76+83=159;
hashFunc(王五)=ASCII(W)+ASCII(W)=87+87=174;
hashFunc(张帅)=ASCII(Z)+ASCII(S)=90+83=173;
 
通过哈希函数映射后,张三应该存储在数组的173下标处,李四存储在159下标,王五和张帅同理。
 
假如只有这4个学生信息需要进行存储,那这个Hash函数设计的很糟糕。因为它浪费了大量的存储空间。下标到了174,那该哈希表数组至少需要开辟174个学生对象的存储空间,然而空间利用率只有4/174,不到3%。
 
另外,根据Hash函数计算结果之后,hashFunc(张三)和hashFunc(张帅)具有相同的地址173,意味着会有一个学生的信息被覆盖,这种现象称作冲突,对于174个存储空间中只需要存储4条记录就发生了冲突,所以这样的Hash函数设计是很不合理的。
 
所以在构造Hash函数时应尽量考虑关键字的分布特点来设计函数使得Hash地址随机均匀地分布在整个地址空间当中。

通常有以下几种构造Hash函数的方法:

1 直接定址法:
取关键字或者关键字的某个线性函数为Hash地址,即hashFunc(key)=a*key+b;例如知道学生的学号从1000开始,最大为4000,则可以将hashFunc(key)=key-1000作为Hash地址。
 
2 平方取中法:
对关键字进行平方运算,然后取结果的中间几位作为Hash地址。假如有以下关键字序列{421,423,436},平方之后的结果为{177241,178929,190096},那么可以取中间的两位数{72,89,00}作为Hash地址。
 
3 折叠法:
将关键字拆分成几部分,然后将这几部分组合在一起,以特定的方式进行转化形成Hash地址。假如知道图书的ISBN号为8903-241-23,可以将hashFunc(key)=89+03+24+12+3作为Hash地址。
 
4 除留取余法:
如果知道Hash表的最大长度为m,可以取不大于m的最大质数 p,然后对关键字进行取余运算,hashFunc(key)=key%p。(在这里p的选取非常关键,p选择的好的话,能够最大程度地减少冲突,p一般取不大于m的最大质数。)

4.哈希表大小的确定

Hash表大小的确定也非常关键,如果Hash表的空间远远大于最后实际存储的数据个数,则造成了很大的空间浪费,如果选取小了的话,则容易造成冲突。在实际情况中,一般需要根据最终数据存储个数和关键字的分布特点来确定Hash表的大小。还有一种情况时可能事先不知道最终需要存储的记录个数,则需要动态维护Hash表的容量(扩容),此时可能需要重新计算Hash地址。

5.冲突的解决

上述哈希函数设计的例子中,发生了冲突现象,因此需要解决该问题,否则数据无法进行正确的存储。通常情况下有2种解决办法:

1 开放定址法:
  即当一个关键字和另一个关键字发生冲突时,使用某种探测技术在Hash表中形成一个探测序列,然后沿着这个探测序列依次查找下去,当碰到一个空的单元时,则插入其中。
  比较常用的探测方法有线性探测法,比如有一组关键字{12,13,25,23,38,34,6,84,91},Hash表长为12,Hash函数为hashFunc(key)=key%11,当插入12,13,25时可以直接插入到下标为1,2,3的位置上,而当插入23时,地址1被占用了,发生冲突,因此沿着地址1依次往下探测(探测步长可以根据情况而定):(1+1)%11=2,依旧冲突,继续嗅探(2+1)%11=3,仍然冲突继续嗅探(3+1)%11=4,此时探测到地址4,发现为空,则将23插入其中,这里的每次嗅探加的1可以看做我们定的步长。
 
2 链地址法:
  采用数组和链表相结合的办法,将Hash地址相同的数据存储在同一张线性表中。这样在哈希表相当于一个链表数组,通过哈希地址得到的是链表表头,所有哈希地址相同的数据,不断的插入到该地址处的链表中。如上述例子中,采用链地址法形成的Hash表存储表示为:
在这里插入图片描述
虽然我们能够采用一些办法去减少冲突,但是冲突是无法完全避免的。因此需要根据实际情况选取解决冲突的办法。

6.哈希表的实现

通过上述的除留取余法构造哈希函数,和链地址法解决冲突,实现一个简易哈希表,类似HashMap:

package hash;

import java.util.ArrayList;

/** * 哈希表 * @param <E>不确定链表节点数据类型,用泛型占位 */
public class HashTable<E> {
   
    private HTLinkedList[] linkedListArray;
    private int size;

    public HashTable(int size){
   
        this.size = size;
        //初始化linkedListArray空间
        linkedListArray = new HTLinkedList[size];
        //初始化linkedListArray链表节点
        for (int i = 0; i < size; i++) {
   
            linkedListArray[i] = new HTLinkedList();
        }
    }

    /** * 数据以键值对的形式存储 * 哈希函数:哈希地址=键字符串的首尾字母的ASCII码值的和 % size * @param key * @return */
    public int hashFunc(String key){
   
        char firstChar = key.charAt(0);
        char lastChar = key.charAt(key.length()-1);
        return (firstChar+lastChar) % size;
    }

    /** * 以key-value形式添加数据 * @param key * @param value */
    public void add(String key,E value){
   
        int index = hashFunc(key);
        linkedListArray[index].add(new Node(key, value));
    }

    public E get(String key){
   
        int index = hashFunc(key);
        Node node = linkedListArray[index].find(key);
        return (E)node.value;
    }

    public void show(){
   
        for (int i = 0; i < size; i++) {
   
            System.out.print("哈希表中下标为"+i+"处的链表中数据为:");
            linkedListArray[i].show();
            System.out.println("");
        }
    }



    public static void main(String[] args) {
   
        HashTable<Integer> hashTable = new HashTable<>(10);
        hashTable.add("key1",1);
        hashTable.add("key2",2);
        hashTable.add("key3",3);
        hashTable.add("key4",4);
        hashTable.add("key5",5);
        hashTable.add("key6",6);
        hashTable.add("key7",7);
        hashTable.add("key8",8);
        hashTable.add("key9",9);
        hashTable.add("key10",10);
        hashTable.add("aaa",11);
        hashTable.add("bbb",12);
        hashTable.add("ccc",13);
        hashTable.add("ddd",14);
        hashTable.add("eee",15);
        hashTable.add("fff",16);
        hashTable.add("ggg",17);
        hashTable.show();
    }

}



/** * 节点类 */
class Node{
   
    public String key;
    public Object value;
    public Node next;
    public Node(String key, Object value){
   
        this.key = key;
        this.value = value;
    }
}

/** * 链表类 */
class HTLinkedList{
   

    //头节点
    private Node head;

    /** * 链表添加节点 * @param node */
    public void add(Node node){
   
        if (head == null){
   
            head = node;
            return;
        }
        Node curNode = head;
        while (curNode.next!=null){
   
            curNode = curNode.next;
        }
        curNode.next = node;
    }

    /** * 查找链表中节点 * @param key * @return */
    public Node find(String key){
   
        Node curNode = head;
        while (curNode!=null){
   
            if (curNode.key.equals(key)){
   
                return curNode;
            }
            curNode = curNode.next;
        }
        return null;
    }

    public void show(){
   
        if (head==null){
   
            System.out.print("空");
            return;
        }
        Node curNode = head;
        while (curNode!=null){
   
            System.out.print("->"+curNode.value);
            curNode = curNode.next;
        }
    }

    /** * 删除、更新操作略 */

}

7.哈希表总结

优点:

1.不论哈希表中有多少数据,查找、插入、删除(有时包括删除)只需要接近常量的时间即O(1) 的时间级。实际上,这只需要几条机器指令。
2.哈希表运算得非常快,在计算机程序中,如果需要在一秒种内查找上千条记录通常使用哈希表(例如拼写检查器)哈希表的速度明显比树快,树的操作通常需要O(N)的时间级。哈希表不仅速度快,编程实现也相对容易。
3.如果不需要有序遍历数据,并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

缺点:

它是基于数组的,数组创建后难于扩展,某些哈希表被基本填满时,性能下降得非常严重,所以程序员必须要清楚表中将要存储多少数据,或者准备好定期地把数据转移到更大的哈希表中,这是个费时的过程。

本文来源MrKorbin,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/25277

发表评论