设计RandomPool结构 【题目】 设计一种结构，在该结构中有如下三个功能： insert(key)：将某个key加入到该结构，做到不重复加入。 delete(key)：将原本在结构中的某个key移除。 getRandom()： 等概率随机返回结构中的任何一个key。
【要求】 Insert、delete和getRandom方法的时间复杂度都是O(1)
import java.util.HashMap; import java.util.Random; public class C01_RandomPoll { public static class Pool<Key>{ //HashMap<K, String>这里的K表示只要是同一种类型就OK了，但并没有指定是哪一种类型 //例如我需要放String的类型，那第一个放进去的时候，K就被指定为String 了 //理论上是更为强大的 HashMap<Key, Integer>keyIndexMap; HashMap<Integer, Key>indexKeyMap; int size; public Pool(){ keyIndexMap = new HashMap<Key, Integer>(); indexKeyMap = new HashMap<Integer, Key>(); } //插入到pool public void insert(Key k){ keyIndexMap.put(k, size); indexKeyMap.put(size++, k); } //删除（这个结合文末的图片提示来看） public void delete(Key key){ if(!keyIndexMap.containsKey(key)){ return ; } int lastIndex = --this.size; int deleteIndex = keyIndexMap.get(key); Key lastKey = indexKeyMap.get(lastIndex); keyIndexMap.put(lastKey, deleteIndex); indexKeyMap.put(deleteIndex, lastKey); keyIndexMap.remove(lastKey); } //获取随机 public Key getRandom(){ if(size==0){ return null; } Random random = new Random(); int index = random.nextInt(keyIndexMap.size()); return indexKeyMap.get(index); } //test public static void main(String[] args) { Pool<String> pool = new Pool<String>(); pool.insert("laoganma"); pool.insert("nengandie"); pool.insert("yyziii"); pool.insert("aaaaaa"); for (int i = 0; i < 10; i++) { System.out.println(pool.getRandom()); } pool.delete("nengandie"); System.out.println("======="); for (int i = 0; i < 10; i++) { System.out.println(pool.getRandom()); } } } }