题目 #

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

思路1 #

分析 #

key是int的hashMap，那不是直接初始化一个int大小的数组，直接索引就好了
没值的是-1，那就直接初始化为-1
尝试出来最大的key是1000000，那就直接上代码

代码实现 #

 1package main
 2
 3type MyHashMap struct {
 4	data []int
 5}
 6
 7func Constructor() (this MyHashMap) {
 8	this.data = make([]int, 1e6 + 1)
 9	for i := range this.data {
10		this.data[i] = -1
11	}
12	return
13}
14
15func (this *MyHashMap) Put(key int, value int) {
16	this.data[key] = value
17}
18
19func (this *MyHashMap) Get(key int) int {
20	return this.data[key]
21}
22
23func (this *MyHashMap) Remove(key int) {
24	this.data[key] = -1
25}
26
27/**
28 * Your MyHashMap object will be instantiated and called as such:
29 * obj := Constructor();
30 * obj.Put(key,value);
31 * param_2 := obj.Get(key);
32 * obj.Remove(key);
33 */

思路2 #

分析 #

上面方法纯属搞笑，忽略即可，只是因为思维局限在使用数组实现hash，嫌数组实现链表太麻烦不想写，没有想到可以直接使用链表
正常hashMap使用数组和链表进行实现
除数使用素数，找了个1000以内的最大素数也就是997

代码实现 #

 1package main
 2
 3import (
 4	"container/list"
 5)
 6
 7const base = 997
 8
 9type dataT struct {
10	key   int
11	value int
12}
13
14type MyHashMap struct {
15	data []list.List
16}
17
18func Constructor1() (this MyHashMap) {
19	this.data = make([]list.List, base, base)
20	return
21}
22
23func (this *MyHashMap) Put(key int, value int) {
24	h := key % base
25	for e := this.data[h].Front(); e != nil; e = e.Next() {
26		if et := e.Value.(dataT); et.key == key {
27			e.Value = dataT{key, value}
28			return
29		}
30	}
31	this.data[h].PushBack(dataT{key, value})
32}
33
34func (this *MyHashMap) Get(key int) int {
35	h := key % base
36	for e := this.data[h].Front(); e != nil; e = e.Next() {
37		if et := e.Value.(dataT); et.key == key {
38			return et.value
39		}
40	}
41	return -1
42}
43
44func (this *MyHashMap) Remove(key int) {
45	h := key % base
46	for e := this.data[h].Front(); e != nil; e = e.Next() {
47		if et := e.Value.(dataT); et.key == key {
48			this.data[h].Remove(e)
49			return
50		}
51	}
52}
53
54/**
55 * Your MyHashMap object will be instantiated and called as such:
56 * obj := Constructor();
57 * obj.Put(key,value);
58 * param_2 := obj.Get(key);
59 * obj.Remove(key);
60 */