哈希函数

基本概念：

• out = f( in )
• in输入域，默认是无穷的；out输出域，有限的
• 相同的输入返回相同的输出值（哈希函数中没有随机的成分）
• 不同的输入可能会产生相同的输出（哈希碰撞，概率非常低）
• 哈希函数的散列性：哈希函数要维持输出域的均匀性与离散性（近似的输入数据映射到输出域上在整个输出域上是均匀的，离散的，即输出的差别很大）

应用
例：大量数据的统计
若在有1 ~ 2 ^ 32的数据中统计不同数字出现的次数

• 常规思路：使用hashMap（key，value），key是对应的数字，value是key出现的次数，但若key很多会造成空间的大量使用
• 优化：将数字先使用哈希函数进行一次映射，再将映射的结果进行模100的操作，将数据分成100份分别去统计，统计完一份就释放空间进行下一次的统计。这样空间就可以缩小100倍

哈希表

基本概念：

• 数据经过哈希函数得到某个整数型值，将该数据存入对应的哈希表：就是将哈希函数得到的值对哈希表对应的数值取模，经计算后存入对应位置，方便查找
• 根据哈希哈希函数的散列性，哈希链表的长度应该是均匀增长的
  
• 如图是模16的哈希表，若数据量过大，则选择扩容为模32的，重新计算每个节点对应的位置
• 在哈希表中增，删，查找数据的时间复杂度都是O(1)的，只是常数项很大。若哈希表已有 n 个数据链的最大长度为 k 则扩容的时间复杂度为（logn），以k为底的n次

题目：设计RandomPool结构

• 思路：增删操作在HashMap中都可以完成，重要的是实现随机放回的功能
  （1）建立两个HashMap，一个为< key, size >，另一个为 < size，key>，其中size为目前哈希表中的元素个数
  （2）getRandom操作便可以通过随机数产生 0 ~ size - 1范围的数字通过 < size，key>的哈希表获得key
  （3）在delete操作时为了保证 0 ~ size - 1位置上的连续性，要将最后一个位置的元素填充到删除位置，size在减一

    public static class Pool<Key>{private HashMap<Key, Integer> keyIndexMap;private HashMap<Integer, Key> indexKeyMap;private int size;public Pool(){//初始化this.keyIndexMap = new HashMap<>();this.indexKeyMap = new HashMap<>();this.size = 0;}public void insert(Key key){if (!keyIndexMap.containsKey(key)){//建立 key 与 size直接的双射关系keyIndexMap.put(key, size);indexKeyMap.put(size, key);size++;}}public void delete(Key key){if (keyIndexMap.containsKey(key)){//为了保证 0 ~ size - 1的连续性//keyIndexMap中删除 <key, deleteIndex>，加入 <lastKey，deleteIndex>//indexKeyMap中删除 <lastIndex, lastKey>，更新 <deleteIndex，lastKey>int deleteIndex = keyIndexMap.get(key);int lastIndex = --size;Key lastKey = indexKeyMap.get(lastIndex);keyIndexMap.remove(key);indexKeyMap.remove(lastIndex);keyIndexMap.put(lastKey, deleteIndex);indexKeyMap.put(deleteIndex, lastKey);}}public Key getRandom(){if (size == 0){return null;}// 0 ~ size - 1的随机数int random = (int)(Math.random() * size);return indexKeyMap.get(random);}}public static void main(String[] args) {Pool<String> pool = new Pool<>();pool.insert("l");pool.insert("j");pool.insert("k");System.out.println(pool.getRandom());}

• 结果演示