706. 设计哈希映射

考点

• 哈希表与链表的综合

题解

class MyHashMap {
	private:
		const static int len = 32768;
		struct Node {
			int key;
			int value;
			Node(int _key, int _value): key(_key), value(_value) {}
		};
		vector<list<Node> > hashMap;
		int getHash(int key) {
			return (key ^ (key >> 16)) & (len - 1);
		}
	public:
		MyHashMap() : hashMap(len) {}

		void put(int key, int value) {
			int h = getHash(key);
			for (auto it = hashMap[h].begin(); it != hashMap[h].end(); it++) {
				if (it->key == key) {
					it->value = value;
					return;
				}
			}
			hashMap[h].emplace_front(key, value);
		}

		int get(int key) {
			int h = getHash(key);
			for (auto it = hashMap[h].begin(); it != hashMap[h].end(); it++) {
				if (it->key == key) {
					return it->value;
				}
			}
			return -1;
		}

		void remove(int key) {
			int h = getHash(key);
			for (auto it = hashMap[h].begin(); it != hashMap[h].end(); it++) {
				if (it->key == key) {
					hashMap[h].erase(it);
					return;
				}
			}
		}
};

思路

和705. 设计哈希集合类似，修改一下双向链表的节点结构即可