// template <typename K, typename V> classMyHashMap { public: /** Initialize your data structure here. */ MyHashMap() { length = 0; v.resize(20); } /** value will always be non-negative. */ voidput(int key, int value){ // ref from http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html // As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. // Higher values decrease the space overhead but increase the lookup cost (reflected in most of the // operations of the HashMap class, including get and put). // The expected number of entries in the map and its load factor should be taken into account when setting // its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is // greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur. if(double(length / v.size()) > 0.5) expand(); int idx = hash(key); auto head = v[idx]; auto tmp = head; while(tmp) { if(key == tmp -> key) { tmp -> value = value; return; } tmp = tmp -> next; } Node* node = new Node(key, value); node -> next = head; v[idx] = node; length++; } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ intget(int key){ // int idx = hash(key); Node* node = v[hash(key)]; while(node) { if(key == node -> key) return node -> value; node = node -> next; } return-1; } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ voidremove(int key){ int idx = hash(key); auto node = v[idx]; Node* prev = NULL; while(node) { if(key == node -> key) { --length; prev ? prev -> next = node -> next : v[idx] = node -> next; } prev = node; node = node -> next; } } private: structNode; vector<Node*> v; int length; // Dynamic resizing voidexpand(){ vector<Node*> tmp(v.size()); v.swap(tmp); v.resize(v.size() * 2); length = 0; for(auto &node : tmp) { while(node) { put(node -> key, node -> value); node = node -> next; } } } // knuth multiplicative hash inthash(int key){ return (longlong)key * 2654435761 % v.size(); }
/** * Your MyHashMap object will be instantiated and called as such: * MyHashMap* obj = new MyHashMap(); * obj->put(key,value); * int param_2 = obj->get(key); * obj->remove(key); */