[数据结构与算法]数据结构---哈希表基本操作浅记

什么是哈希表？

哈希表就是借鉴了数组的随机访问能力，利用数组的随机访问的高效性产生了哈希表

哈希函数其实就是把任意的数据类型转成数组的索引

e.g. char --> int? ? ? ?char - 'a' = int

????????大的int类型转为小的int类型 一般都是取模操作，根据数论摸一个素数

????????String --> int? ? ? ? ? ?字符串的内部就是字符数组，因此还是按照字符转为int的方式

????????其他类型 -- > int? ? ? 因为任意的数据类型都有toString方法，所以可以先转为String --> int

什么是哈希冲突？

不同的两个key值，经过哈希函数的运算得到了两个相同的索引。

在理论上，数学中的任意函数f(x),两个不相同的x都一定有可能会映射到相同的y，哈希冲突无法避免！

怎们解决哈希冲突？

1.闭散列：

当发生冲突时，找到冲突位置的旁边是否存在空闲位置，直到找到第一个空闲位置放入元素。

好存难查更难删，工程中很少使用此方案

图解:?

?

查找：

要查找120时，先120 %101 = 19,发现19这个位置存放的不是120，则继续向后找，直到找到120位置，若一直向后遍历走完整个数组还没找到，则这个元素不存在。

若整个哈希表冲突非常严重，此时查找一个元素从O(1)=>遍历数组O(n)。所以一般不用

2.开散列：

?

查找任意元素:

如果取模后若冲突，遍历链表。 在最坏情况下，开散列方案遍历链表，相较于闭散列方案查找次数会大大降低，元素删除，查找，链表的对应操作，相较于闭散列方案来说容易很多。

若遇见最最最坏的情况，若当前哈希表中某个位置，比如图中19这个位置冲突非常严重，恰好每个元素取模后都是19，某个数组对应的链表的长度过长，查找效率就会降低。面对这种情况一般有两种解决方案：

1.针对整个数组进行扩容(比如现在数组长度101，扩容到202)就会由原先%101 => %202，很多原来同一个链表上的元素均分到其他新的位置，降低哈希冲突。 e.g. C++中的STL的Map

2.将这个冲突严重的链表再次变为新的哈希表/二分搜索树(将O(n) => O(logn))不用整张哈希表进行处理，只处理冲突严重的链表。 e.g. JDK的方案

?第二种方法如图：

?

练习题：

已知一个线性表(38，25，74，63，52，48)，假定采用散列函数h (key) = key%7计算散列地址，并散列存储在散列表A[...6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（C）

????????A.1.5???????????????????????????????? B.1.7???????????????????????????????? C.2.0 ????????????????????????????????D.2.3

?

解：

成功查找的平均查找长度为：?当前表中所有元素的查找次数 / 表中有效的元素个数 --> 12/6 =2

?拓展：开散列时：

?

小结：

对于一般场景下的哈希函数的设计:

一般来说不用自己写，用现成的即可。MD5,MD4,MD3 SHA1,SHA256 MD5—般用在字符串计算hash值的特点:

1.定长。无论输入的数据有多长，得到的MD5值长度固定。

2.分散。如果输入的数据稍有偏差，得到的MD5值相差很大(冲突概率非常低，工程领域忽略不计)

3.不可逆。根据字符串计算md5很容易，想通过得到的md5还原字符串到底是啥非常难(基本不可能)

4.根据相同的数据计算的md5值稳定的，不会发生变化。 稳定性是所有哈希函数都要满足的特点

MD5用途：

1.作为hash运算

⒉.用于加密

3.对比文件内容(内容稍有修改，得到的md5值天差地别)。上传下载。

?自己设计一个开散列代码：

完整代码：

import java.util.NoSuchElementException;

/**
 * @Author qiqichongya
 * @Date 2022/8/14 19:20
 * @PackageName:HashMap
 * @ClassName: HashMapTest
 * @Description: 自己设计一个 开散列
 */
public class MyHashMap {
    // 有效节点数
    private int size;
    // 实际存储元素的 Node 数组
    private Node[] hashTable;
    // 取模数
    private int M;
    // 负载因子
    private static final double LOAD_FACTOR = 0.75;


    public MyHashMap() {
        this(16);
    }

    public MyHashMap(int init) {
        this.hashTable = new Node[init];
        this.M = init;
    }

    /**
     * 对key求哈希值
     *
     * @param key
     * @return
     */
    public int hash(int key) {
        return Math.abs(key) % M;
    }

    /**
     * 将一对
     *
     * @param key
     * @param val
     */
    public int put(int key, int val) {
        // 1.先取模找到key对应的Node数组中的索引下标。
        int index = hash(key);
        // 2.遍历对应索引下标的链表，查询key是否已经存在
        for (Node x = hashTable[index]; x != null; x = x.next) {
            if (x.key == key) {
                int oldValue = x.value;
                x.value = val;
                return oldValue;
            }
        }
        // 此时说明该键值对是一个新的，需要新增节点头插到哈希表中
        // 也就是说 此时 Node x == null --> hashTable[index] == null --> 还没有放值。
        Node node = new Node(key, val);
        node.next = hashTable[index];
        hashTable[index] = node;
        size++;
        if (size >= hashTable.length * LOAD_FACTOR) {
            expansion();
        }
        return val;
    }

    /**
     * 数组扩容为原来的二倍 和 搬移数据
     */
    private void expansion() {
        // 1.产生一个新的数组并且长度是原来长度的二倍。
        Node[] newTable = new Node[hashTable.length << 1];
        // 2.进行元素的搬移操作，此时取模应该为新的数组长度
        this.M = newTable.length;
        for (int i = 0; i < hashTable.length; i++) {
            for (Node x = hashTable[i]; x != null; ) {
                // 求出 x 在新的数组中的索引下标
                int index = hash(x.key);
                Node next = x.next;
                // 在新数组中进行头插
                x.next = newTable[index];
                newTable[index] = x;
                // 继续搬移剩下的链表节点。
                x = next;
            }
        }
    }

    /**
     * 判断key是否存在
     *
     * @param key
     * @return
     */
    public boolean containsKey(int key) {
        int index = hash(key);
        for (Node x = hashTable[index]; x != null; x = x.next) {
            if (x.key == key) {
                return true;
            }
        }
        return false;
    }

    /**
     * 判断value是否存在
     *
     * @param value
     * @return
     */
    public boolean containsValue(int value) {
        // 全表扫描
        for (int i = 0; i < hashTable.length; i++) {
            for (Node x = hashTable[i]; x != null; x = x.next) {
                if (x.value == value) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 在哈希表删除指定键值对（key,value）
     *
     * @param key
     * @param value
     * @return
     */
    public boolean remove(int key, int value) {
        // 先拿到当前 key 在数组中的索引
        int index = hash(key);
        // 判断头节点是不是待删除节点
        Node head = hashTable[index];
        if (head.key == key && head.value == value) {
            // 此时头节点就是待删除节点
            hashTable[index] = head.next;
            size--;
            return true;
        }
        // 此时头节点不是待删除节点
        Node prev = hashTable[index];
        while (prev.next != null) {
            if (prev.next.key == key && prev.next.value == value) {
                // 此时当前节点是待删除节点的前驱节点
                Node current = prev.next;
                prev.next = current.next;
                size--;
                return true;
            } else {
                prev = prev.next;
            }
        }
        // 哈希表中没有这个节点
        throw new NoSuchElementException("no such node!remove error");
    }
}

class Node {
    // 对key进行hash运算
    int key;
    int value;
    // 下一个节点的地址
    Node next;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

查找：

    /**
     * 判断key是否存在
     *
     * @param key
     * @return
     */
    public boolean containsKey(int key) {
        int index = hash(key);
        for (Node x = hashTable[index]; x != null; x = x.next) {
            if (x.key == key) {
                return true;
            }
        }
        return false;
    }

    /**
     * 判断value是否存在
     *
     * @param value
     * @return
     */
    public boolean containsValue(int value) {
        // 全表扫描
        for (int i = 0; i < hashTable.length; i++) {
            for (Node x = hashTable[i]; x != null; x = x.next) {
                if (x.value == value) {
                    return true;
                }
            }
        }
        return false;
    }

哈希表删除指定键值对：

    /**
     * 在哈希表删除指定键值对（key,value）
     *
     * @param key
     * @param value
     * @return
     */
    public boolean remove(int key, int value) {
        // 先拿到当前 key 在数组中的索引
        int index = hash(key);
        // 判断头节点是不是待删除节点
        Node head = hashTable[index];
        if (head.key == key && head.value == value) {
            // 此时头节点就是待删除节点
            hashTable[index] = head.next;
            size--;
            return true;
        }
        // 此时头节点不是待删除节点
        Node prev = hashTable[index];
        while (prev.next != null) {
            if (prev.next.key == key && prev.next.value == value) {
                // 此时当前节点是待删除节点的前驱节点
                Node current = prev.next;
                prev.next = current.next;
                size--;
                return true;
            } else {
                prev = prev.next;
            }
        }
        // 哈希表中没有这个节点
        throw new NoSuchElementException("no such node!remove error");
    }