Random Hash DS

Implement a set-like data structure with three methods:

• Insert an element

• Remove an element (by value); and

• Return an element chosen uniformly at random

e.g. After inserting 1, 3, 7, 2 and 9 in that order, we could remove 7, and the random number would be one of {1, 3, 2 or 9} each with 25% probability.

• Brain storm:

  • Binary tree: Constant space with logN insertions and deletions, and O(N) random returns.

  • Hash table

    • O(1) inserts and deletes.

    • O(N) random

int main() {
    unordered_set<int> s;
    for (auto i : { 1,2,3,4,5,6,7 }) {
        s.insert(i);
    }

    srand(time(nullptr));

    while (1) {
        int random = rand() % s.size();
        auto iter = s.begin();
        std::advance(iter, random);
        cout << *iter << endl;
        pause();

    }

}

• Working off this idea, once thing we can do is use a secondary hash structure, like an vector (which support O(1) removal and deletions by index).

• Essentially we use the secondary vector as a container that reverses the order of our map structure. Our map is <value, index> and our vector is <index, value>. Using these two details, we can find both the value or index, in O(1) time. Removals are just swapping and removing things from the end, and modifying our map to accommodate that.

class rand_hash{
public:
    rand_hash() : size(0) {
        srand(time(nullptr));
    }

    void insert(int element) {
        map.insert(make_pair(element, size++));
        vect.push_back(element);
    }

    void remove(int element) {
        if (map.find(element) == map.end()) return;

        // adjust vector elements
        // 1) get the index to delete from the main map
        int rem_index = map.find(element)->second;
        // 2) index to the vector and replace it with last element
        vect.at(rem_index) = vect.back();
        // 3) remove last element
        vect.erase(vect.begin() + size - 1);

        // adjust map
        // 1) Remove element
        map.erase(element);
        // 2) Fix modified element index
        map.find(vect.at(rem_index))->second = rem_index;

        size--;
    }

    int random() {
        int index = rand() % size;
        int findthis = vect.at(index);

        return map.find(findthis)->first;
    }

    void print() {
        for (auto i : map)
            cout << i.first << ":" << i.second << " ";
        pause();
    }

    void print_vec() {
        for (auto i : vect) cout << i << " ";
        pause();
    }

private:
    // value -> index
    unordered_map<int, int> map;
    vector<int> vect;

    int size;
};


int main() {
    rand_hash map;
    for (auto i : { 0,1,2,3,4,5,6 }) {
        map.insert(i);
    }
    map.print();

    map.remove(3);
    map.remove(4);
    map.print();

    while (1) {
        cout << map.random() << " ";
        pause();
    }
}