哈希表（Hash Table）

基础概念 #

哈希表是一种常见的数据结构，也叫散列表。哈希表最大的优点是高效，在哈希表中插入、删除或查找一个元素都只需要 O(1) 的时间。

因此，哈希表经常被用来优化时间效率。除了专门考散列表的题，也经常作为辅助计算的数据结构，很多时候都可以考虑是否需要借助散列表解决。比如用来记录字符串中字母出现的次数、字符串中字符出现的位置等信息。

哈希函数 #

设计哈希表的前提是待存入的元素需要一个能计算自己哈希值的函数，哈希表根据每个元素的哈希值把它存储到合适的位置。

抗碰撞性 #

在衡量哈希函数安全性方面，主要是考虑算法的抗碰撞性，即：

弱抗碰撞性：找到和该消息具有相同散列值的另外一条消息。
强抗碰撞性：找到两条散列值相同的不同消息。

数据结构 #

JavaScript 和 Go 中都有内置对象 Map 的实现，可以直接用。

JavaScript 实现 #

使用上，Map 只能通过 has、get 和 set 获取数据，而不能用对象的方式。

let m = new Map()

m['a'] = 1
m.set('b', 2)
m.get('b')

console.log(m)//Map(1) { 'b' => 2, a: 1 }
console.log(m['a'])//1
console.log(m.has('a'))//false
console.log(m.get('a'))//undefined

还有一些不太常用的方法。

clear #

移除 Map 对象中的所有元素。

delete #

移除 Map 对象中指定的元素。

entries #

返回一个新的包含 [key, value] 对的 Iterator 对象，返回的迭代器的迭代顺序与 Map 对象的插入顺序相同。

forEach #

按照插入顺序依次对 Map 中每个键/值对执行一次给定的函数。

function logMapElements(value, key, map) {
  console.log(`m[${key}] = ${value}`);
}

new Map([['foo', 3], ['bar', {}], ['baz', undefined]])
  .forEach(logMapElements);

// expected output: "m[foo] = 3"
// expected output: "m[bar] = [object Object]"
// expected output: "m[baz] = undefined"

keys #

返回一个引用的 Iterator 对象。它包含按照顺序插入 Map 对象中每个元素的 key 值。

values #

返回一个新的 Iterator 对象。它包含按顺序插入 Map 对象中每个元素的 value 值。

Golang 实现 #

Go 的实现没有多余接口，需要自己判断元素是否在 map 中。

package main

func main() {
	m := make(map[string]string)
	m["hello"] = "world"
	m["foo"] = "bar"

	for i, v := range m {
		println(i, v)
	}

	if v, exist := m["not-found"]; !exist {
		println("not exist")
	} else {
		println(v)
	}
}
//hello world
//foo bar
//not exist

底层实现 #

如果哈希表的键的数目是固定的，并且数目不太大，那么也可以用数组来模拟哈希表，数组的下标对应哈希表的 key 的哈希值，而数组的值与哈希表的值 value 对应，实际上一些底层实现也是这样的原理。