算法设计与分析 哈希函数与哈希表

算法设计与分析 哈希函数与哈希表

哈希函数与哈希表

哈希函数哈希表题目：设计RandomPool结构

哈希函数

基本概念：

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{
        private HashMap keyIndexMap;
        private HashMap 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中删除 ，加入 
                //indexKeyMap中删除 ，更新 
                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 pool = new Pool<>();
        pool.insert("l");
        pool.insert("j");
        pool.insert("k");
        System.out.println(pool.getRandom());
    }

结果演示