一个系列彻底搞懂map(一):hash表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

const (
	stateEmpty = iota	//空状态
	stateOccupied		//占用状态
	stateDeleted		//删除状态
	defaultSize = 128	//初始默认桶的个数
)

type pair struct {
	state int 		//bucket状态
	key   int		//键
	value int		//值
}

// 每个桶存取一个键值对
type HashMap struct {
	buckets []pair	// 桶
	count int		// 键值对个数
}

func NewHashMap() *HashMap {
	return &HashMap{
		buckets: make([]pair, defaultSize),
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

// hash函数采用最简单的取模
func (hm *HashMap) hash(key int) int {
	return key % len(hm.buckets)
}

// inSet设为true代表执行Set操作
// 当执行Set操作时，找到存储key的桶、或者第一个空桶、或者Delete状态的桶，就结束遍历
// 当执行Get、Del操作时，碰到存储key的桶或者第一个空桶就结束遍历
func (hm *HashMap) access(key int, inSet bool) (p *pair) {
	h := hm.hash(key)
	for i := 0; i < len(hm.buckets); i++ {
		bucket := hm.buckets[h]
		if !inSet && bucket.state == stateDeleted ||
			bucket.state == stateOccupied && bucket.key != key {
			h = (h + 1) % len(hm.buckets)
			continue
		}
		p = &hm.buckets[h]
		break
	}
	return
}

 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

func (hm *HashMap) set(key int, value int) {
	p := hm.access(key, true)
    //如果终止迭代的桶为非占用桶，即为空桶或者已被删除的桶，我们需要插入KV
	if p.state != stateOccupied {
		hm.count++
		p.state = stateOccupied
		p.key = key
	}
    //否则，只需要更新value
	p.value = value
}

func (hm *HashMap) Set(key int, value int) {
    //如果负载因子过大，就需要扩容
	if hm.needGrow() {
		hm.grow()
	}
	hm.set(key, value)
}

func (hm *HashMap) Del(key int) {
	p := hm.access(key, false)
    //终止于空桶，说明map并未存取该key
	if p.state == stateEmpty {
		return
	}
	hm.count--
	p.state = stateDeleted
}

func (hm *HashMap) Get(key int) (val int, ok bool) {
	p := hm.access(key, false)
    //终止于空桶，说明map并未存取该key
	if p.state == stateEmpty {
		return
	}
	return p.value, true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// 哈希表扩容
func (hm *HashMap) grow() {
	oldbuckets := hm.buckets
	//桶数量倍增
	hm.buckets = make([]pair, len(oldbuckets)<<1)
	hm.count = 0
	for i := 0; i < len(oldbuckets); i++ {
		bucket := oldbuckets[i]
		if bucket.state == stateOccupied {
            //将旧桶数据插入新桶
			hm.set(oldbuckets[i].key, oldbuckets[i].value)
		}
	}
}

// 负载因子>0.25时就扩容
func (hm *HashMap) needGrow() bool {
	return hm.count*4 >= len(hm.buckets)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

const defaultSize = 1024

//存取键值对的链表节点，每个节点存取一个键值对
type node struct {
	key   int
	value int
	next  *node
}

type bucket node

type HashMap struct {
	buckets []bucket	//桶，每个桶还是链表的头结点，头结点实际不存取数据
	count   int
}

func NewHashMap() *HashMap {
	return &HashMap{
		buckets: make([]bucket, defaultSize),
	}
}

 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

func (m *HashMap) hash(key int) int {
	return key % len(m.buckets)
}

//头插法插入节点
func (m *HashMap) set(key int, value int, hash int) {
	m.count++
	m.buckets[hash].next = &node{
		key:   key,
		value: value,
		next:  m.buckets[hash].next,
	}
}

func (m *HashMap) Set(key int, value int) {
	if m.needGrow() {
		m.grow()
	}
    //先通过哈希值找到对应桶
	h := m.hash(key)
    //再遍历桶后同义词链表，查找key是否存在，如果存在则只需更新value即可
	for n := m.buckets[h].next; n != nil; n = n.next {
		if n.key == key {
			n.value = value
			return
		}
	}
    //否则插入键值对
	m.set(key, value, h)
}

//查询
func (m *HashMap) Get(key int) (value int, ok bool) {
	h := m.hash(key)
    // 定位到桶后，顺序遍历桶后链表
	for n := m.buckets[h].next; n != nil; n = n.next {
		if n.key == key {
			return n.value, true
		}
	}
	return
}

//删除
func (m *HashMap) Del(key int) {
	h := m.hash(key)
	for n := (*node)(&m.buckets[h]); n.next != nil; n = n.next {
		tmp := n.next
		if tmp.key == key {
			n.next = tmp.next
			m.count--
		}
	}
}

//负载因子>=1就扩容
func (m *HashMap) needGrow() bool {
	return m.count >= len(m.buckets)
}

func (m *HashMap) grow() {
	oldbuckets := m.buckets
    //倍增
	m.buckets = make([]bucket, len(m.buckets)<<1)
	m.count = 0
	for i := 0; i < len(oldbuckets); i++ {
		bucket := oldbuckets[i]
		for n := bucket.next; n != nil; n = n.next {
			m.set(n.key, n.value, m.hash(n.key))
		}
	}
}