哈希函数与哈希表
哈希函数
基本概念：
- 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()); }
- 结果演示
