上期填坑
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();
}
}
hash的概念
哈希又称为
散列，将任意长度的输入值（key）通过哈希函数转换成固定长度的输出值（value），该输出即是哈希值，通过该哈希值，可以快速存储和搜索数据。
通过该定义可以看到hash的三个组成部分：
输入值（key）：hash的输入，字符串或者整数；哈希函数：hash的关键，用于将key值通过不同算法映射到固定长度的hash值；哈希值：哈希函数的输出，也叫哈希索引，该索引指向的就是储存的数据。
三个组成部分的关系如下图所示：
哈希函数的特性
- 一致性：相同的输入应该产生相同的哈希值。
- 高效性：计算哈希值的速度应该足够快。
- 离散性：哈希函数应该能将输入空间均匀地映射到输出空间，减少冲突。
- 抗碰撞性：不同的输入应该尽可能地产生不同的哈希值，以减少冲突的概率。
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] 是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中 任何一个 。题目测试用例保证存在与输入对应的答案。
