C++简单实现HashMap_c++中hash_map怎么写

实现说明

1. 线程不安全；
2. 2倍扩容，方便使用位运算计算桶位置；但存在极端情况下的弊端；
3. 不支持将链表转为红黑树

源码

#pragma once
#include<string>

//Hash函数
int Hash(int key) {
	return key;
}

//线程不安全容器
//2倍扩容，方便计算
//不支持链表转为红黑树
class HashMap {
	class Node {
	public:
		const int key;
		int val;
		const int hash;
		Node* next = NULL;
		Node(int hash,int key,int val):hash(hash),key(key),val(val){

		}

		Node* findNode(const int& key) {
			Node* node = this;
			while (node != NULL && node->key != key)
				node = node->next;
			return node;
		}
	};
	using NodePtr = Node*;
	NodePtr* table;

	const double load_factor = 0.75;  //负载因子
	int threshold = 12;  //扩容阈值：load_factor*size
	int size = 1<<4;  //table大小
	int maxSize = 1 << 30;  //table最大尺寸
	int count = 0;  //当前元素

	//2倍扩容
	void resize() {
		if (size >= maxSize) return;
		int newSize = size << 1;
		NodePtr* newTable = new NodePtr[newSize];
		memset(newTable, 0, newSize * sizeof(NodePtr));
		for (int i = 0; i < size; ++i) {
			Node* node = table[i];
			while (node != NULL) {
				int index = node->hash & (newSize - 1);
				Node* tmp = node->next;
				node->next = newTable[index];
				newTable[index] = node;
				node = tmp;
			}
		}
		std::swap(newTable, table);
		size = newSize;
		threshold = size * load_factor;
		delete[] newTable;
	}

	//增加count
	void addCount(int x) {
		count += x;
		if (count > threshold)
			resize();
	}

public:
	HashMap() {
		table = new NodePtr[size];
		memset(table, 0, size * sizeof(NodePtr));
	}
	~HashMap() {
		for (int i = 0; i < size; ++i) {
			Node* node = table[i];
			while (node != NULL) {
				Node* tmp = node->next;
				delete node;
				node = tmp;
			}
			table[i] = NULL;
		}
		delete[] table;
	}
	HashMap(const HashMap&) = delete;
	HashMap& operator=(const HashMap&) = delete;
	
	//获取值,
	//不存在key，返回false
	bool get(int key, int& value) {
		int hash = Hash(key);
		Node* node = NULL;
		int index = hash & (size - 1);
		if (table[index] != NULL)
			node = table[index]->findNode(key);
		if (node != NULL) value = node->val;
		return node != NULL;
	}

	//放入值
	void put(int key, int value) {
		int hash = Hash(key);
		Node* node = NULL;
		int index = hash & (size - 1);
		if (table[index] != NULL)
			node = table[index]->findNode(key);
		if (node != NULL) node->val = value;
		else {
			node = new Node(hash, key, value);
			node->next = table[index];
			table[index] = node;
			addCount(1);
		}
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115