浅谈hash函数及应用

一、Hash(散列函数)

Hash一般被翻译成散列、杂凑或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列出相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。（介绍来源于百度百科）

Hash函数性质：

输入为任意长度字符串，输出为固定长度字符串。
输入确定，输出也确定。特定输入对应唯一输出（有可能两个输入对应一个输出——hash碰撞，解决碰撞有链地址法和开发地址法，这里就不展开了，就浅谈一下就好了）
随着输入域的增大，输出域均匀增大（这种均匀性越好，hash函数越好）

二、设计RandomPool结构

Problem

【题目】

设计一种结构，在该结构中有如下三个功能：

insert(key)：将某个key加入到该结构，做到不重复加入。

delete(key)：将原本在结构中的某个key移除。

getRandom()：等概率随机返回结构中的任何一个key。

【要求】

insert、delete和getRandom方法的时间复杂度都是O(1)

solution

insert：

构造map<key,Integer> keyIndexMap，map<Integer,key> indexKeyMap。当第一个插入o1，就在keyIndexMap.add（o1,1）,indexKeyMap.add(1,o1)。

getRandom：

通过数字进行random，得到的就是等概率的。（保证0~Integer是连续的就可以保证等概率）。

delete：

删除后存在空位，这些空位会影响到0~Integer是连续的。解决办法：拿最后一条记录填补空位。

code

/**
 * @author god-jiang
 * @date 2020/1/4
 */
public class RandomPool {
    public static class Pool<K>{
        private HashMap<K,Integer> keyIndexMap;
        private HashMap<Integer,K> indexKeyMap;
        //size记录第几个进来的
        private int size;
        public Pool(){
            keyIndexMap = new HashMap<>();
            indexKeyMap = new HashMap<>();
            size = 0;
        }
        //插入操作分别插入到keyIndexMap和indexKeyMap中
        public void insert(K key){
            if(!keyIndexMap.containsKey(key)){
                 keyIndexMap.put(key,size);
                indexKeyMap.put(size++,key);
            }

        }
        
        // A 0 0 A
        // B 1 1 B
        // C 2 2 C
        // D 3 3 D
        //先确定删除的索引，以及最后面的值，把最后面的值补充到删除的地方
        //之后删除开始应该删除的
        public void delete(K key){
            if(keyIndexMap.containsKey(key)){
                int deleteIndex = keyIndexMap.get(key);
                int lastIndex = --size;
                K lastKey = indexKeyMap.get(lastIndex);
                keyIndexMap.put(lastKey,deleteIndex);
                indexKeyMap.put(deleteIndex,lastKey);
                keyIndexMap.remove(key);
                indexKeyMap.remove(lastIndex);
            }
        }
        
        //等概率从indexKeyMap返回key
        public K random(){
            if(size==0){
                return null;
            }
            int num = (int) (Math.random()*size);
            return indexKeyMap.get(num);
        }
    }
}