[数据结构与算法]基于CRC64的通用哈希表(HashMap)的实现（使用golang）

简介

学过数据结构的同学可能知道，哈希（hash）是数据查询的最快方式。具有$O(1)$的时间复杂度。
原理如下：

首先需要定义一个哈希函数（又称散列函数），它的功能是把我们要存的数据x, 映射到数组上的某一个位置y。例如：

$$y=x\%19$$

这个时候会有一个问题：会有多个x映射到同一个y。假设$x_1=7,x_2=19$, 那么它们经过上述映射后都会放在数组下标7的位置
$$\begin{gathered} x_1\%19=7 \\ {x}_2\%19=7 \end{gathered}$$

这时就会产生冲突。解决冲突的办法有：

• 开地址法：
  • 线性探测
  • 二次探测
  • 再哈希
• 链地址法

已有的博文对相关知识的介绍已经清晰易懂，本文不再赘述。但大多重在理论，而轻实践，示例代码多是教学性质的，无法实际用于生产环境。经过本人的观察，具有以下问题：

• 只支持单一的数据类型。实际中，我们不可能为每种类型都实现一个hashmap,
• 使用非常简单的散列函数。例如上述的取模。实际上，取模运算对整数类型的数据散列情况比较好，不支持其它类型。

本文就这两个问题进行解决，首先是使用泛型来支持任意类型，然后使用CRC64散列函数将任意二进制数据散列到64位整数再对数组长度取模。由于CRC64具有良好的散列性质，因此实现的哈希表不容易出现冲突。

原理

我们使用链地址法解决冲突。如下图：
数组中每个元素都相当于是一个链表， 当某个位置发生冲突时，直接把数据挂在链表上即可。
假设哈希表中已经有了16， 18两个数据，现在需要把32放入，经过哈希函数映后应该放在数据下标为0的位置。那把32放入链表中元素16后面即可。

在Java语言（版本1.8）中，HashMap也是使用链地址法解决冲突，当链表长度大于8时，链表将转换成红黑树。显然红黑树的平衡性质使得在红黑树上查找一个元素远快于链表。但是我认为如果能够选择一个较均匀的哈希函数，那么链表长度通常不会很长（3左右），使用红黑树提升的性能并不明显。

哈希函数有如下选择：

• DJB2 系列
• FNV 系列
• SDBM
• CRC32、CRC64
• Murmur 系列

有人已经测过这些函数的各种性能，包括碰撞率、速度、多种数据集上的分散程度：

• Which hashing algorithm is best for uniqueness and speed?

还有一些比较新的哈希函数，如SipHash、HighwayHash、xxHash、MetroHash：

• 漫谈非加密哈希算法

本文选择碰撞率看起来较少的CRC64。读者可根据实际性况选择。

实现

基于go 进行实现

结构

首先定义链表的结点结构。next表示下一结点，key表示用来作索引的键，value表示数据。

type _HashEntry[K comparable, V interface{}] struct {
	next  *_HashEntry[K, V]
	key   K
	value V
}

接下来定义HashMap的结构。其中需要维护一个array数组，数组的数据类型为链表结点的指针。
size表示哈希表中数据的个数。

type HashMap[K comparable, V interface{}] struct {
	threshhold    int                 //  数组长度超过此阈值则扩容
	inflateFactor float64             //  百分比，扩容时需要用
	array         []*_HashEntry[K, V] //  数组
	size          int                 //  实际数据量
}

然后是HashMap的构造函数。
初始的数组大小为16，指定当数组使用率 inflateFactor为75%时，数组需要扩容。threshhold由以下公式计算得到，为了避免多次计算下面的公式，实际是根据它来判断是否需要扩容的。

$$\mathrm{threshhold}=\mathrm{len}(\mathrm{array})\times \mathrm{inflateFactor}$$

func NewHashMap[K comparable, V interface{}]() *HashMap[K, V] {
	initSize := 16
	return &HashMap[K, V]{
		threshhold:    12,
		inflateFactor: 0.75,
		array:         make([]*_HashEntry[K, V], initSize),
		size:          0,
	}
}

哈希函数

实现得比较粗暴，接直将结构体转字符串，然后字符串转二进制。再利用go自带的crc64包散列得到无符号整数。

func hash(key interface{}) uint64 {
	var table = crc64.MakeTable(crc64.ECMA)
	bytesBuffer := bytes.NewBuffer([]byte{})
	switch key.(type) {
	case string:
		str := key.(string)
		err := binary.Write(bytesBuffer, binary.BigEndian, []byte(str))
		if err != nil {
			panic("invalid key!")
		}
	default:
		err := binary.Write(bytesBuffer, binary.BigEndian, []byte(fmt.Sprintf("%v", key)))
		if err != nil {
			panic("invalid key!")
		}
	}
	return crc64.Checksum(bytesBuffer.Bytes(), table)
}

获取大小

直接返回size即可

func (this *HashMap[K, V]) Size() int {
	return this.size
}

放置数据

首先利用哈希函数计算哈希值，因为是一个无符号整数，范围非常大，因此再对数组长度取模确定最终位置 index。

放入数组中的链表中后，数据量加1，如果发现数据量大小 size 大于等于threshhold, 则扩充数组。如何扩充数组，将在下面介绍。

func (this *HashMap[K, V]) Set(key K, value V) {
	index := hash(key) % uint64(len(this.array))
	node := &_HashEntry[K, V]{
		key:   key,
		value: value,
	}
	if this.array[index] == nil {
		this.array[index] = node
	} else {
		for i := this.array[index]; i != nil; i = i.next {
			if i.key == key {
				i.value = value
				break
			}
			if i.next == nil {
				i.next = node
			}
		}
	}
	this.size++
	if this.size >= this.threshhold {
		this.inflate()
	}
}

取数据

计算得到位置后，遍历数据取出即可。

func (this *HashMap[K, V]) Get(key K) (V, bool) {
	index := hash(key) % uint64(len(this.array))
	if this.array[index] == nil {
		return *new(V), false
	}

	for node := this.array[index]; node != nil; node = node.next {
		if node.key == key {
			return node.value, true
		}
	}
	return *new(V), false
}

删数据

计算得到位置后，从链表中删除结点，size 减1

func (this *HashMap[K, V]) Delete(key K) {
	index := hash(key) % uint64(len(this.array))
	if this.array[index] == nil {
		return
	}
	if this.array[index].key == key {
		this.array[index] = this.array[index].next
		this.size--
		return
	}
	for node := this.array[index]; node.next != nil; node = node.next {
		if node.next.key == key {
			node.next = node.next.next
			this.size--
			return
		}
	}
}

数组扩充

当数据量大小size 到一定程度时（由inflateFactor和threshhold决定），需要扩充数组以较少哈希冲突。

这一步将重新生成一个长度为原来两倍的数组，然后遍历原数组，将所有数据重新放入新的数组中。

/*
*
扩充表格，并重新hash所有数据
*/
func (this *HashMap[K, V]) inflate() {
	if len(this.array) <= (1 << 61) {
		newLength := len(this.array) * 2
		newThresh := int(float64(newLength) * this.inflateFactor)
		oldArray := this.array
		this.threshhold = newThresh
		this.array = make([]*_HashEntry[K, V], newLength)
		this.size = 0
		// re hashing
		for i := 0; i < len(oldArray); i++ {
			for node := oldArray[i]; node != nil; node = node.next {
				this.Set(node.key, node.value)
			}
		}
	}
}

测试

下面代码测试了以上实现的正确性：

func TestHashMap(t *testing.T) {
	m := structure.NewHashMap[int, string]()

	for i := 0; i < 100; i++ {
		m.Set((i), fmt.Sprint(i+100))
		fmt.Println("insert: ", i)
	}

	m.Delete(38)
	m.Delete(54)
	m.Delete(86)
	m.Delete(101)
	m.Delete(-1)

	for i := 0; i < 100; i++ {
		v, ok := m.Get((i))
		if ok {
			fmt.Println(v)
		} else {
			fmt.Println("error !")
		}
	}

	fmt.Println("size:", m.Size())
}

结果：