一、哈希函数

（1）性质

• 哈希函数的输入域无限大，但是输出域有限
• 哈希函数的返回值不是随机的，相同的输入必定有相同的输出。
• 不同的输入也有可能有相同的输出（哈希碰撞）
• 哈希函数的返回值在输出域上是均匀分布的，模上一个数M,那么在M-1上的分布也是均匀的（重要）

二、哈希表

（1）简介

输入一个样本通过哈希函数计算后得到的返回值再模上一个数得到的结果对应数组的脚标，数组里是头节点，每当有一个样本计算得到一个数就在对应位置的的头节点后面把样本挂上去，形成一个链表，相当于每个数组的位置都存着一个链表（散列链表）

（2）java中实现的结构

• HashMap
• HashSet
  ps:早期Java数组每个位置后面是链表，现在数组每个后面是一颗红黑树

（3）特性

哈希表的增删改查的时间复杂度都是O（1）

三、练习

题目：设计RandomPool结构，该结构具有以下三个功能：

• insert（key）:将某个Key加入该结构，做到不重复加入
• delete（key):将原本在结构中的某个key移除
• getRandom（）：等概率随机返回结构中的任何一个key

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

解题思路：准备两个HashMap，和一个index（第几个进入），一个HashMap存（key,index）另一个存（index,Key）。存的时候就正常的往两个HashMap里存，删的时候由于直接删的时候在0到index之间的数会缺少产生缺少随机数的时候会有为空的情况，所以在删除的时，先用最后位置的数把坑填上，然后把最后位置上的数据删掉就可以了，随即返回key的方法就是在0到index的范围产生一个随机然后获取随机数代表的key就可以了

代码示例：

public class RandomPool<K> {
private HashMap<K,Integer> keyIndexMap;
private HashMap<Integer,K> indexKeyMap;
private int index;
public  RandomPool() {
    keyIndexMap=new HashMap<K,Integer>();
    indexKeyMap=new HashMap<Integer,K>();
    index=0;
}

public void insert(K key) {
    if(!keyIndexMap.containsKey(key)) {
    keyIndexMap.put(key,index);
    indexKeyMap.put(index++,key);
    }
}
public void delete(K key) {
    if(keyIndexMap.containsKey(key)) {
    int deleteIndex=keyIndexMap.get(key);
    int lastIndex=--index;
        K lastKey=indexKeyMap.get(lastIndex);
    keyIndexMap(lastKey,deleteIndex);
        indexKeyMap(deleteIndex,lastKey);
    keyIndexMap.remove(key);
    indexKeyMap.remove(lastIndex);
    }
}
public K getRandom() {
    int randomIndex=(int)(Math.random()*index);
    return indexKeyMap.get(randomIndex);
}
}