哈希——设计RandomPool结构

设计一种结构，在该结构中有如下三个功能：
insert(key)：将某个key加入到该结构，做到不重复加入。
delete(key)：将原本在结构中的某个key移除。

getRandom()：等概率随机返回结构中的任何一个key。
【要求】 Insert、 delete和getRandom方法的时间复杂度都是O(1)

解：使用两个hash表进行操作，

map1中存放的 key value 分别是相应的值和对应的插入顺序

map2中正好相反， key value 分别是对应的插入顺序，和相应的值

insert(key)：即是上面的操作方法

getRandom()：就是利用size，使用Math.random() * size 产生一个随机数，范围就是[0, size )的一个值，然后从map2中获取相应的数字对应的值即可

delete(key)：需要注意的是，如果直接在map1和map2中进行删除操作的话，会产生很多空缺的地方，此时，如果getRandom()的话，产生的随机数的位置很可能是空的，这样就不能保证O(1)的时间复杂度

正确的做法是：（将最后一个覆盖到相应的删除位置）若删除的是其中位置x处的值，则把map1中倒数第一个value赋为删除处的value（即为插入元素的次序），把map2中应该删除的次序的位置的value也赋成倒数第一个的值

并且删除对应位置上的值

public class RandomPool {
    Map<String, Integer> keyIndexMap;
    Map<Integer, String> indexKeyMap;
    int size;


    public RandomPool(){
        this.keyIndexMap = new HashMap<>();
        this.indexKeyMap = new HashMap<>();
        this.size = 0;
    }

    public void insert(String str){
        if(!keyIndexMap.containsKey( str )){
            keyIndexMap.put(str, size);
            indexKeyMap.put( size++, str );
        }
    }

    public String getRandom(){
        if(size == 0){
            return null;
        }
        int randomIndex = (int) (Math.random() * size);
        System.out.println(randomIndex);

        return indexKeyMap.get(randomIndex);

    }

    public void delete(String str){
        //如果包含这个值的话，就把map中最后那一个值赋到当前这个位置，然后size--，最后要删除相应位置上的值
        if(keyIndexMap.containsKey( str )){
            int deleteIndex = keyIndexMap.get(str);
            String lastKey = indexKeyMap.get(--size);
            keyIndexMap.put(lastKey, deleteIndex);
            indexKeyMap.put( deleteIndex, lastKey );

            keyIndexMap.remove(str);
            indexKeyMap.remove(size);
        }
    }

    public void printKeyIndexMap(){
        for(Map.Entry<String, Integer> entry : keyIndexMap.entrySet()){
            System.out.println("Key: " + entry.getKey() + " value: " + entry.getValue());
        }
    }

    public void printIndexKeyMap(){
        for(Map.Entry<Integer, String> entry : indexKeyMap.entrySet()){
            System.out.println("Key: " + entry.getKey() + " value: " + entry.getValue());
        }
    }



    public static void main(String[] args){
        RandomPool randomPool = new RandomPool();

        randomPool.insert( "a" );
        randomPool.insert( "b" );
        randomPool.insert( "c" );
        randomPool.insert( "d" );
        randomPool.insert( "e" );
        randomPool.insert( "f" );
        randomPool.insert( "g" );
        randomPool.insert( "h" );

        randomPool.printKeyIndexMap();
        System.out.println();
        randomPool.printIndexKeyMap();
        System.out.println();


        randomPool.insert( "asdfef" );

        randomPool.printKeyIndexMap();
        System.out.println();
        randomPool.printIndexKeyMap();
        System.out.println();


        System.out.println(randomPool.getRandom());

        randomPool.delete( "g" );


        randomPool.printKeyIndexMap();
        System.out.println();
        randomPool.printIndexKeyMap();
        System.out.println();
    }
}

哈希——设计RandomPool结构

推荐阅读