哈希表

哈希表的概念

本文所说的哈希表是一种基于数组的数据结构，它可以快速的进行数据的插入和删除操作。

哈希表的优缺点

优点：不论哈希表中有多少数据，插入和删除的只需要接近常量的时间，即O(1)的时间复杂度。
缺点：哈希表底层是基于数组的，数组有最大容量，所以当哈希表接近满容量时，性能下降的很严重，所以在使用哈希表之前最好可以清楚表中需要存储多少数据，或者有将哈希表进行扩容的策略（这是一个耗时的操作）；哈希表不支持遍历。

所以如果不需要进行遍历，且可以提前知道数据的大小，那么哈希表在速度和易用方面还是无以伦比的。

哈希化与哈希函数

哈希表的精髓就在于怎么把数据的关键值映射成为数组下标，这里就需要使用哈希函数来完成这个过程，这个过程就叫做哈希化，一般也可以叫做散列函数和散列过程。哈希函数被广泛用在很多地方，比如加密、校验、分布式、负载均衡、数据库索引等，java的基类中也声明了hashcode方法来返回对象的哈希码值。

那么给出一串字符串或者数字，如何利用哈希函数去计算它的数组下标呢，哈希算法有很多，常见的有幂乘法、移位法、折叠法和取模法，以下采用取模法。

取模法：
例如：数组的容量为10（smallRange），数据为范围0~199的数字（largeNum），那么数字对应这个数组的哈希地址为：
smallNum = largeNum % smallRange
即将关键值对数组容量取余，比如数字为179，对数组容量10取余为9，那么它的数组下标即为9
这样就把一个大范围的数据压缩对应为一个固定的小范围数据，就完成了哈希化的过程

冲突

如果两个不同的数，比如19和179，对10取余的结果都为9，都对应了数组下标为9的那个地址，那么怎么为它们分配位置呢，这就产生了冲突。

如何更好地避免与解决冲突也是评判哈希表性能的一个重要指标。

避免冲突首先需要将数组的容量设置的比需要储存的数据量大一些，一般是两倍于需要存储的数据量，其次数组的容量最好可以是一个质数，最后选用一个散列效果更好的哈希函数。
选取一个质数是为了在取余的时候更加均匀分布，例如：2 4 6 8 10 12这6个数，如果对6取余得到 2 4 0 2 4 0 只会得到3种HASH值，冲突会很多。如果对7取余得到 2 4 6 1 3 5 得到6种HASH值，没有冲突。

解决冲突的方法有两种：
1.开放地址法
2.链地址法

开放地址法

之前说过，数组的容量比需要存储的数据量要大一些，一般设置为两倍，那么数组中就会存在一些“空洞”，当一个数在求得hash值之后发现对应的数组下标位置已经被占了，那么它会去“找”其他空着的位置，在找下一个空白单元的时候，有三种方法可供使用：线性探测、二次探测和再哈希法

1.线性探测
采用线性探测法，在发生冲突时，后插入的数据会线性的去探测数组的空白单元，简单来说就是按着数组下标递增的顺序一步一步的查找（当达到数组容量最大值会归零），发现空白单元后就被安排进去。

还是0~199范围数字插入到10容量的数组中的这个例子，179已经插入到了数组下标为9的单元中，再插入19的时候，产生了冲突，如果采用线性探测的方法，19就会去找下标0的位置有没有数据，如果已经有数据在那个位置了，它就会去找下标1的位置，直至找到空白单元为止。

下面来看一下线性探测法的代码实现：
首先定义一个数据类DataItem，用来存放数据，简单起见，这个类就只有一个int类型变量

public class DataItem {

    private int data;

    public DataItem(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }
}

然后是HashTable类，实现哈希表和及其操作：

/**
 * 哈希表，解决冲突的方法为：开放地址法，线性探测，探测步长为：1
 */
public class HashTable {

    private DataItem[] hashArray;       //哈希表底层的数组
    private int tableSize;      //哈希表的大小，即为数组容量
    private DataItem nonItem;   //删除的时候自己定义的一个空对象，代表删除标志位，查找的时候会跳过这个标志位

    //构造方法，初始化变量
    public HashTable(int size) {
        tableSize = size;
        hashArray = new DataItem[tableSize];
        nonItem = new DataItem(-1);
    }

    //哈希表的打印方法
    public void displayTable() {
        System.out.print("Table: ");
        for (int i = 0; i < tableSize; i++) {
            if (hashArray[i] != null) {
                System.out.printf(hashArray[i].getData() + " ");
            } else {
                System.out.printf("** ");
            }
        }
        System.out.println();
    }

    //哈希函数：哈希表的灵魂，这里采用取模法
    public int hashFunc(int key) {
        return key % tableSize;
    }

    //插入哈希表的方法
    public void insert(DataItem item) {
        int key = item.getData();
        int hashVal = hashFunc(key);        //对插入哈希表的数据求哈希值

        //当遇到冲突的时候进行线性探测，即哈希值自加一，探测步长为：1
        while (hashArray[hashVal] != null && hashArray[hashVal].getData() != -1) {
            ++hashVal;
            hashVal %= tableSize;   //这里对表大小取模是防止哈希值超过表的大小，也可以判断之后归零
        }

        hashArray[hashVal] = item;   //将数据插入到合适的位置
    }

    //移除操作，传入关键值
    public DataItem delete(int key) {
        int hashVal = hashFunc(key);    //计算关键值的哈希值

        //如果第一次没找到说明发生了冲突，需要线性探测
        while (hashArray[hashVal] != null) {
            if (hashArray[hashVal].getData() == key) {
                DataItem temp = hashArray[hashVal];
                hashArray[hashVal] = nonItem;
                return temp;
            }
            ++hashVal;
            hashVal %= tableSize;
        }
        return null;
    }

    //查找方法，其实插入和删除中都包含查找方法，只不过各有不同
    public DataItem find(int key) {
        int hashVal = hashFunc(key);

        while (hashArray[hashVal] != null) {
            if (hashArray[hashVal].getData() == key) {
                return hashArray[hashVal];
            }
            ++hashVal;
            hashVal %= tableSize;
        }
        return null;
    }
}

HashTableApp是一个测试类：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class HashTableApp {

    public static void main(String[] args) throws IOException{
        DataItem dataItem;
        int key, size, n, keysPerCell;

        System.out.printf("Enter size of hash table: ");
        size = getInt();    //从终端获取哈希表大小
        System.out.printf("Enter initial number if items: ");
        n = getInt();       //获取初始的容量的大小
        keysPerCell = 10;   //指定数据关键字的范围

        HashTable theHashTable = new HashTable(size);   //创建一个哈希表

        //根据初始容量和关键字范围随机生成一些数据插入哈希表
        for (int j = 0; j < n; j++) {
            key = (int)(Math.random() * keysPerCell * size);
            dataItem = new DataItem(key);
            theHashTable.insert(dataItem);
        }

        //一个终端的输入界面，调用哈希表的各个方法
        while (true) {
            System.out.printf("Enter first letter of show, insert, delete, or find: ");
            char choice = getChar();
            switch (choice) {
                case 's':
                    theHashTable.displayTable();
                    break;
                case 'i':
                    System.out.printf("Enter key value to insert: ");
                    key = getInt();
                    dataItem = new DataItem(key);
                    theHashTable.insert(dataItem);
                    break;
                case 'd':
                    System.out.printf("Enter key value to delete: ");
                    key = getInt();
                    theHashTable.delete(key);
                    break;
                case 'f':
                    System.out.printf("Enter key value to find: ");
                    key = getInt();
                    dataItem = theHashTable.find(key);
                    if (dataItem != null) {
                        System.out.println("Found " + key);
                    } else {
                        System.out.println("Could not find " + key);
                    }
                    break;
                default:
                    System.out.printf("Invalid entry\n");

            }
        }


    }

    public static String getString() throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = br.readLine();
        return s;
    }

    public static char getChar() throws IOException {
        String s = getString();
        return s.charAt(0);
    }

    public static int getInt() throws IOException {
        String s = getString();
        return Integer.parseInt(s);
[图片上传中...(完全二叉树与非完全二叉树.png-156b6c-1544770237296-0)]
    }
}

下图是测试结果：

线性探测的哈希表测试结果图.png

聚集：线性探测法有一个弊端，就是会产生聚集，比如说179已经插入到了数组下标9的单元，19按照线性探测的方法就会插入到下标为0的单元中，这时如果再插入数字10或是29，都会被安排到数组下标为1的单元，一个小的聚集就形成了，更可怕的是聚集会越滚越大，这一连串已经填充数据的单元叫做填充序列，聚集就是指随着数据的增多，填充序列越来越长，如下图所示：

聚集产生的说明图.jpg

聚集会导致非常长的探测长度，这在操作哈希表的过程中时非常耗时的。当哈希表越来越满的时候，聚集也会变得越来越严重，所以在设计哈希表容量的时候一般确保存储的数据量不会超过数组容量的一半，最多到2/3，这个概念就做负载因子。
为了解决线性探测中的聚集问题，可以采用二次探测和再哈希法

2.二次探测
二次探测的探测序列不再是线性的了，而是采用跳跃式的探测方式，比如采用步长是与原始下标距离平方的方式，公式为：
hashVal = hashVal + k * k（k为探测的次数）
例如19在插入的时候发现179已经占用了数组下标为9的单元，根据以上公式第一次探测的探测步长为1的平方，如果发现下标为0的单元也被占用了，则说明这里可能发生了小的聚集，那么第二次探测就会加大步长为2的平方4，那么就会探测数组下标为4的单元是否被占用，以此类推，直到找到空白的单元并插入进去。
下图为二次探测的图例，为了看出效果，使用了容量为20的数组

二次探测.png

二次探测会产生二次聚集问题，因为所有映射到同一位置的关键字在寻找空位的时候，探测的单元都是一样的。
二次探测是实现代码在线性探测的基础上稍作修改即可，不做展示。

3.再哈希法
之前说了二次探测会导致二次聚集是因为冲突的关键字探测序列都是一样的，那如何根据不同的关键字来定制不同的探测序列的，这就是再哈希法的关键：对冲突的关键字再求hash值作为探测步长

第二次求hash值得哈希函数公式为：stepSize = constant - （key % constant）
constant一般取小于数组容量的一个质数，stepSize为探测步长
例如：数组容量为10，插入数字19的时候发现数组下标为9的单元被179占用了，按照公式，constant取值小于10的一个质数7，那么探测步长为：7 - （19 % 7）= 2，当插入29的时候探测步长为：7 - （29 % 7）= 6，这样就可以根据不同的关键字来分配不同的探测序列。

实现代码
DataItem类：数据对象类

public class DataItem {

    private int data;

    public DataItem(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }
}

HashDoubleTable类：采用再哈希化方法解决聚集问题

/**
 * 由于采用开放地址法的哈希表会产生聚集，导致数据插入效率低下
 * 解决方法是：二次探测和再哈希化
 * 本类采用再哈希化:stepSize = constant - (key % constant)
 */
public class HashDoubleTable {

    private DataItem[] arrayTable;
    private int tableSize;
    private DataItem nonItem;


    public HashDoubleTable(int size) {
        tableSize = size;
        arrayTable = new DataItem[tableSize];
        nonItem = new DataItem(-1);
    }

    public void displayTable() {
        System.out.printf("Table: ");
        for (int j = 0; j < tableSize; j++) {
            if (arrayTable[j] != null) {
                System.out.printf(arrayTable[j].getData() + " ");
            } else {
                System.out.printf("** ");
            }
        }
        System.out.println();
    }

    //第一个哈希函数，用来对key值取哈希值
    public int hashFunc1(int key) {
        return key % tableSize;
    }

    //如果发生了冲突，对key值再次取哈希值，stepSize = constant - (key % constant)
    //constant取小于数组容量的质数
    public int hashFunc2(int key) {
        return 5 - key % 5;
    }

    /**
     * insert方法中唯一的不同点就是在发生冲突后，
     * 探测不再是线性探测，而采用第二个哈希函数算出不同的步长
     * 以防发生聚集
     * @param item
     */
    public void insert(DataItem item) {
        int data = item.getData();

        int hashVal = hashFunc1(data);
        int stepSize = hashFunc2(data);     //根据关键值算出探测步长

        while (arrayTable[hashVal] != null && arrayTable[hashVal].getData() != -1) {
            hashVal += stepSize;        //当发生冲突时就按照探测步长探测下一个单元
            hashVal %= tableSize;       //防止探测溢出数组容量
        }
        arrayTable[hashVal] = item;     //将数据插入到合适的单元
    }


    //delete方法中的探测方法也是再哈希化
    public DataItem delete(int key) {
        int hashVal = hashFunc1(key);
        int stepSize = hashFunc2(key);
        DataItem temp;

        while (arrayTable[hashVal] != null) {
            if (arrayTable[hashVal].getData() == key) {
                temp = arrayTable[hashVal];
                arrayTable[hashVal] = nonItem;     
                return temp;
            } else {
                hashVal += stepSize;
                hashVal %= tableSize;
            }
        }
        return null;
    }

    //采用在哈希化计算探测步长
    public DataItem find(int key) {
        int hashVal = hashFunc1(key);
        int stepSize = hashFunc2(key);

        while (arrayTable[hashVal] != null) {
            if (arrayTable[hashVal].getData() == key) {
                return arrayTable[hashVal];
            } else {
                hashVal += stepSize;
                hashVal %= tableSize;
            }
        }
        return null;
    }
}

以上是采用开放地址法来解决冲突，而更为常见的是采用链地址法解决冲突。

链地址法

链地址法是一种数组+链表的数据结构，每个数组单元对应一个链表，当发生冲突时，数据会插入对应数组下标的链表中，如下图所示：

链地址法的哈希表.png

哈希函数依然用的是将关键字的值对数组容量取模，但每个数组单元对应的是一个链表而不是一个数据对象。

实现代码
首先实现一个链表
Link链表节点类，封装数据，除了一个int类型的变量，还需要声明一个next引用指向下一个节点

public class Link {

    private int data;       //int类型数据变量
    public Link next;       //引用指向下一个节点

    //构造方法
    public Link(int data) {
        this.data = data;
    }

    //getter
    public int getData() {
        return data;
    }

    //打印节点数据方法
    public void displayLink() {
        System.out.printf(data + " ");
    }
}

SortedList类，一个有序链表类，有序链表可以减少不成功查找时间，在删除和查找时一般仅需要查找一半的链表即可找到对应的数据节点，但是插入的时间增加，数据节点需要插入到合适的位置，可以根据实际情况采用有序或无序链表，

public class SortedList {

    private Link first;     //链表需要一个指向头部节点的连接

    public SortedList() {
        first = null;
    }   //构造方法，初始化链表

    /**
     * 一个打印链表的方法，从头部节点遍历链表
     */
    public void displayList() {
        System.out.printf("List (first-->last): ");
        Link current = first;

        while(current != null) {
            System.out.printf(current.getData() + " ");
            current = current.next;
        }
        System.out.println();
    }

    /**
     * 插入链表的方法，传入一个数据节点
     * @param theLink
     */
    public void insert(Link theLink) {
        Link previous = null;       //previous指向前一个节点
        Link current = first;       //current指向当前节点，从首节点开始
        int key = theLink.getData();    //获取数据节点关键字的值

        while (true) {
            //最后一个节点的next指向null
            //判断是否还在链表内，且当前节点的关键值小于插入的关键值，则移动到下一个节点
            if (current != null && current.getData() < key) {
                previous = current;     //previous指向当前节点
                current = current.next;     //current指向下一个节点
            } else {
                if (current == first) {     //考虑特殊情况，如果是头节点的话需要修改first指向
                    first = theLink;
                } else {        //插入节点第一步：前面一个节点的next指向插入节点
                    previous.next = theLink;
                }
                theLink.next = current;     //插入节点的第二步：插入节点的next指向当前节点
                return;
            }
        }
    }

    /**
     * 链表的移除方法，传入移除的关键值
     * @param key
     */
    public void delete(int key) {
        Link previous = null;       //初始化previous
        Link current = first;       //初始化current

        //判断好在链表内且当前节点的关键值不等于删除的key值
        while (current != null && current.getData() != key) {
            previous = current;     //移动previous
            current = current.next; //移动current
        }
        if (previous == null) {     //如果删除的是头节点，需要修改first指向
            first = first.next;
        } else {
            previous.next = current.next;   //将之前节点的next指向当前节点的next，即从链表中移除当前节点
        }       //垃圾回收器会将删除的节点回收，因为已经没了引用
    }

    /**
     * 链表的查找方法，传入查找的关键值
     * @param key
     * @return
     */
    public Link find(int key) {
        Link current = first;       //current指向头节点

        //当还在链表内且当前节点的值不等于查找的值，则移动到下一个节点
        while (current != null && current.getData() != key) {
            current = current.next;
        }
        if (current.getData() == key) {     //如果找到了，返回当前节点
            return current;
        } else {
            return null;      //找不到就返回null
        }
    }
}

实现链表后再来实现哈希表就很简单了，所需做的就是求出hash值然后调用链表的相应方法
HashTable哈希表的实现类：

/**
 * 此类的哈希表对于冲突的处理方法采用链地址法
 */
public class HashTable {

    private SortedList[] hashArray;     //数组+链表变量
    private int tableSize;      //哈希表大小

    //构造方法，初始化数组+链表
    public HashTable(int size) {
        tableSize = size;
        hashArray = new SortedList[tableSize];
        for (int j = 0; j < tableSize; j++) {
            hashArray[j] = new SortedList();
        }
    }

    //打印哈希表的方法
    public void displayTable() {
        System.out.println("Table: ");
        for (int j = 0; j< tableSize; j++) {
            System.out.printf(j + ". ");
            hashArray[j].displayList();
        }
    }

    //哈希函数：取模法
    public int hashFunc(int key) {
        return key % tableSize;
    }

    //哈希表的插入方法
    public void insert(int key) {
        int hashVal = hashFunc(key);        //求出插入值得hash值
        Link theLink = new Link(key);       //创建链表节点对象
        hashArray[hashVal].insert(theLink);     //调用链表的insert方法插入数据节点
    }

    //哈希表的移除方法
    public void delete(int key) {
        int hashVal = hashFunc(key);        //求出删除关键值得hash值
        hashArray[hashVal].delete(key);     //在hash值对应的数组单元调用链表的移除方法
    }

    //链表的查找方法
    public Link find(int key) {
        int hashVal = hashFunc(key);        //求出hash值
        Link theLink = hashArray[hashVal].find(key);    //调用链表的查找方法
        return theLink;     //返回数据节点
    }
}

HashTableApp哈希表的测试类

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class HashTableApp {

    public static void main(String[] args) throws IOException{
        Link dataItem;
        int key, size, n, keysPerCell;

        System.out.printf("Enter size of hash table: ");
        size = getInt();
        System.out.printf("Enter initial number if items: ");
        n = getInt();
        keysPerCell = 10;

        HashTable theHashTable = new HashTable(size);

        for (int j = 0; j < n; j++) {
            key = (int)(Math.random() * keysPerCell * size);
            theHashTable.insert(key);
        }

        while (true) {
            System.out.printf("Enter first letter of show, insert, delete, or find: ");
            char choice = getChar();
            switch (choice) {
                case 's':
                    theHashTable.displayTable();
                    break;
                case 'i':
                    System.out.printf("Enter key value to insert: ");
                    key = getInt();
                    theHashTable.insert(key);
                    break;
                case 'd':
                    System.out.printf("Enter key value to delete: ");
                    key = getInt();
                    theHashTable.delete(key);
                    break;
                case 'f':
                    System.out.printf("Enter key value to find: ");
                    key = getInt();
                    dataItem = theHashTable.find(key);
                    if (dataItem != null) {
                        System.out.println("Found " + key);
                    } else {
                        System.out.println("Could not find " + key);
                    }
                    break;
                default:
                    System.out.printf("Invalid entry\n");

            }
        }


    }

    public static String getString() throws IOException {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String s = br.readLine();
        return s;
    }

    public static char getChar() throws IOException {
        String s = getString();
        return s.charAt(0);
    }

    public static int getInt() throws IOException {
        String s = getString();
        return Integer.parseInt(s);
    }
}

测试结果图如下：

链地址法哈希表测试结果图.png

哈希表的效率

如果没有发生冲突，那么哈希表的存取的时间可以达到一个常数时间，即时间复杂度为O(1)。
如果发生了冲突，则哈希表的存取时间决定于探测长度，平均探测长度又与负载因子有关，负载因子越大，探测长度越长。
所以在设计和使用哈希表的时候，预测存储数据量和数组容量很关键，另外哈希函数的散列效率也是影响哈希表存取效率的一个重要因素。

参考文章

《Data Structures & Algorithms in Java》 Robert Lafore著