哈希：高效数据存储与检索的关键

上期填坑

leetcode, 1046. 最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);//使用优先队列构建大顶堆
        for (int stone : stones) {
            pq.offer(stone);
        }
    
        while (pq.size() > 1) {//每次取最大的两个石头进行粉碎
            int a = pq.poll();
            int b = pq.poll();
            if (a > b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }
}

哈希.jpg

hash的概念

哈希又称为散列，将任意长度的输入值（key）通过哈希函数转换成固定长度的输出值（value），该输出即是哈希值，通过该哈希值，可以快速存储和搜索数据。
通过该定义可以看到hash的三个组成部分：

输入值（key）：hash的输入，字符串或者整数；

哈希函数：hash的关键，用于将key值通过不同算法映射到固定长度的hash值；

哈希值：哈希函数的输出，也叫哈希索引，该索引指向的就是储存的数据。

三个组成部分的关系如下图所示：

hash.png

哈希函数的特性

一致性：相同的输入应该产生相同的哈希值。
高效性：计算哈希值的速度应该足够快。
离散性：哈希函数应该能将输入空间均匀地映射到输出空间，减少冲突。
抗碰撞性：不同的输入应该尽可能地产生不同的哈希值，以减少冲突的概率。

hash冲突

从hash的定义可以发现一个问题：在同一个hash函数的情况，不同的key值可能映射到相同的hash值上，这就是所谓的hash冲突。hash冲突的多少也是检验函数好坏的标准。
如下图，在hash函数为对hash表大小取模的情况下，key值3和9产生了冲突：

hash冲突.png

解决hash冲突常用的方法有开放寻址和链接法：

链接法：使hash表的每个单元指向具有相同hash值的记录的链表。如图：

链接法.png
开放寻址：所有元素都存储在哈希表本身中。每个表条目包含一条记录或 null。查找元素时，逐个检查表槽，直到找到所需元素或者明确该元素不在表中。而在开放寻址中，产生冲突又有线性探测、二次探测、双重hash等方法，下图给出了线性探测和二次探测的比较：

开放寻址.png

hash的实现

下面给出了hash的简单Java代码示例：

public class MyHashTable<K, V> {
    private static final int DEFAULT_CAPACITY = 10;
    private LinkedList<Entry<K, V>>[] table;
    private int size;

    public MyHashTable() {
        table = new LinkedList[DEFAULT_CAPACITY];
        size = 0;
    }

    // 哈希函数：计算键的哈希值
    private int hash(K key) {
        return Math.abs(key.hashCode()) % table.length;
    }

    // 插入键值对
    public void put(K key, V value) {
        int index = hash(key);
        if (table[index] == null) {
            table[index] = new LinkedList<>();
        }
        for (Entry<K, V> entry : table[index]) {
            if (entry.key.equals(key)) {
                entry.value = value; // 更新值
                return;
            }
        }
        table[index].add(new Entry<>(key, value)); //链接法
        size++;
    }

    // 删除键值对
    public void remove(K key) {
        int index = hash(key);
        if (table[index] != null) {
            for (Entry<K, V> entry : table[index]) {
                if (entry.key.equals(key)) {
                    table[index].remove(entry);
                    size--;
                    return;
                }
            }
        }
    }

    // 获取键对应的值
    public V get(K key) {
        int index = hash(key);
        if (table[index] != null) {
            for (Entry<K, V> entry : table[index]) {
                if (entry.key.equals(key)) {
                    return entry.value;
                }
            }
        }
        return null;
    }

    // 获取哈希表大小
    public int size() {
        return size;
    }

    // 内部类，表示键值对
    private static class Entry<K, V> {
        K key;
        V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}

在hash实现中还需要考虑负载因子（负载因子=哈希表中的元素总数/哈希表的大小）的存在，用来减少hash冲突，提高hash效率，感兴趣可以自己实现看看。

hash的应用

数据存储与查找：hash的快速的插入与查找特性，让其常用于缓存映射以快速访问数据。。Java中的HashMap和HashSet就是基于哈希表实现的。
数据安全与加密：我们熟知的SHA、CRC、MurmurHash、MD5等哈希函数，因其不可逆的特性而适用。
数据校验与文件标志：hash输入的细微变动都会引起hash值的不同，数据敏感的特性使其适用。
负载均衡、数据分片、数据库索引、磁盘等都有hash的身影。

小试牛刀

leetcode, 888. 公平的糖果交换

爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 aliceSizes 和 bobSizes ，aliceSizes[i] 是爱丽丝拥有的第 i 盒糖果中的糖果数量，bobSizes[j] 是鲍勃拥有的第 j 盒糖果中的糖果数量。
两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。
返回一个整数数组 answer，其中 answer[0] 是爱丽丝必须交换的糖果盒中的糖果的数目，answer[1] 是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中任何一个。题目测试用例保证存在与输入对应的答案。