算法 Linear Hash 原理及实现

yfractal · 2020年01月27日 · 最后由 passerby 回复于 2020年04月20日 · 11784 次阅读
本帖已被管理员设置为精华贴

写在前面

这篇我写的比较啰嗦,大家也可以看 Berkeley CS186: Hash-based Indexes

或者直接看实现

写的比较啰嗦的原因,我没有一下子讲清楚 Linear Hash 是什么 😢 ,而是一点一点增加“功能”,比如 bucket_index 唠叨了几次,才唠叨完。

有点类似 tdd 的开发方式,先写一个简单的功能,加测试,再加测试,再改。这样可能会比较方便理解。

以下是正文:

Hash 在计算机中,非常重要。除了会被用来存键值对(key val pair),还会被用作数据库存储索引的数据结构。

简单来说,一个 Hash 会首先申请一个数组,然后通过 hash function 将 key 映射成数组的 index,之后将 key、value 存储到数组内。

那么,有两个地方可能会影响性能。一个是并行,一个是在数组长度不够用的时候,需要创建更大的数组。

Redis 是单线程,Rust 可以使用读写锁。而 Erlang 自带的内存型存储 ETS,使用了 linear hash 作为 key value pair 的存储结构,提供了更好的并行能力。

下面简单介绍一下 Linear Hash 的原理及实现。

Segment & Table

一个 hash 首先会创建一个数组,然后使用 hash function 将 key 映射到对应的位置上去。

一个简单 hash function 可以是

def hash_val(key)
  key.hash % @total_size
end

如果这个数组“满”了的话,我们需要将数组扩大,数组扩大后,由于影响了 @total_size,则需要重新计算 hash 值后,将数据填入到对应的位置里。

很显然,当数据量较大的时候,会非常影响性能。这个过程一般被称为 resizing。

Linear Hash 为了解决这个问题,让一个 hash 可以对应多个数组,每次做 resizing 的时候,只会影响一个数组。

我们将存储的具体内容的结构称为 bucket,我们将由 bucket 组成的数组称为 segment,由 segment 组成的数组称为 table。

用代码表示,大体是这样:

segment0 = [bucket00, bucket00, bucket00, bucket00]
segment1 = [bucket10, bucket10, bucket10, bucket10]

table = [segment0, segment1]

所以,当我们需要查找一个 key 的时候,首先要计算所在的 segment,之后还要计算所在 segment 内的位置。

为了方便叙述,我们假定 segment 的长度为 4,假设 key 都是正整数(这样可以省去 key -> intger 的运算,比较直观)。

先来计算在 bucket 在 segment 内的位置,由于 @total_size 是 4,所以用 key 的 hash 指的二进制的后两位作为 bucket index,

方法如下:

def bucket_index(hash_val)
  hash_val & 3 # 取后两位
end

例如:

hash_val = 3 # hash_val.to_s(2) == "11"
hash_val & 3 = 3 # 11 & 11 = 11 == 3

hash_val = 7 # 111
hash_val & 3 == 3 # 111 & 11 = 11 == 3

现在我们来计算 segment index。

目前,我们有两个 segment,key 的 hash 值的后两位被用来表示再 segment 中的索引。

所以我们用倒数第三位表示 segment index。

代码如下:

def segment_index(hash_val)
  # 对 hash_val 取后 3 位 减去 取后 2 位的值,在向右移两位。
  (hash_val & 7 - hash_val & 3) >> 2
end

为了实现简单,在做 key 到 hash_val 的运算的时候,通过模运算,取到我们能存储的总长度范围之内的值。

相应方法则变为:

def hash_val(key)
  total_buckets = 2 * 4 # table array's size * segment array's size
  key % total_buckets
end

def segment_index(hash_val)
  hash_val >> 2 # drop last 2 bits
end

def bucket_index(hash_val)
  hash_val & 3 # get last 2 bits
end

Solve Conflict

目前,我们每个 segment 的长度为 4,一共有 2 个 segment。

假设我们存入的 key 有:1 和 9,那么通过 hash_val 方法得到的值,都是 1,所以最后得到的位置是一样的,既所谓的 hash value conflict。

为了解决这个问题,我们为每个 segment 增加一个 overflow_segment,当某个 key 的 hash_val 已经存在的时候,

则将 key、val 存到 overflow_segment 内。代码如下:

class Segment
  attr_reader :segment, :overflow_segment

  def initialize
    @segment = []
    @overflow_segment = []
  end

  def put(index, key, val)
    if @segment[index]
      @overflow_segment << [key, val]
    else
      @segment[index] = [key, val]
    end
  end

  def get(index, key)
    bucket = @segment[index] || []

    k, v = bucket[0], bucket[1]

    if k == key
      v
    else
      @overflow_segment.each do |k, v|
        return v if k == key
      end
      nil
    end
  end
end

Dynamic Grow

Split

Linear Hash 会根据情况(下一个章节介绍),动态增加 segment。而且每次 resizing 的时候,只移动一个 segment 内的 buckets。

依旧假设现在有 2 个 segment,分别为 segment0,segment1。未增加 segment 前,对应的最后两位为 0,1

bit    segment
0      segment0
1      segment1

这时候,我们增加一个 segment2,取 hash val 中的 1 位,无法满足需求,所以我们取 2 位,则

bit     segment
00      segment0
x1      segment1
10      segment1

我们假设 segment0 里存的 key 是 0,8。

则在增加 segment 前,对应的值:

key in binary segment index bucket index
0 0000 0 00
8 1000 0 00

存储情况:

bit    segment   overflow_segment
0      [0]             [8] # 忽略 key 对应的 val
1      []

增加 segment 后,取倒数 3、4 为作为 segment index

key in binary segment index bucket index
0 0000 00 00
8 1000 10 00

存储情况:

bit    segment
00      [0] # 忽略 key 对应的 val
x1      []
10      [8]

我们可以看出来,这次 grow,只需要将 segment0 分到一个 new_segment0 和 segment3 里。

之后,用 new_segment0 替换掉之前的 segment0,并将 segment3 放到 table 的末尾即可。

伪代码如下

new_segment0, segment3 = split_segment_with_2_bit_for_segment_index(segment0)
table[0] = new_segment0
table << segment3

Find Location

因为我们增加了 segnment,所以我们需要新的方法找到一个 key 的存储位置。

原来有 2 个 segment,一次 grow 之后,变成了 3 个。

00 segment0
 1 segment1
10 segment2

在 grow 之前,我们仅需要 1 位,就可以定位到对应的 segment。现在有 3 个,所以为了找到 segment 的位置,我们需要 2 位。

2 位二进制,可以表示 0、1、2、3。既可计算出的 segment_index 有 0、1、2、3。

如果,segment_index 为 0、1、2 的时候,我们可以找到对应的 segment。

但如是 3,我们则需要想办法将其映射到 1。

首先 hash_val 需要多计算一位

def hash_val(key)
  slots = 2.pow(2) * 4 * 2
  key % slots
end

bucket_index 不变。

segment_index 依然是去掉后两位,但需要处理两种情况:

如果计算出来的 index 小于当前的 table_size,则返回 index。

如果大于等于 table_size,则说明还没有被分裂出来,则去掉已经计算好的 index 的第一位。

伪代码:

def segment_index(hash_val)
  index = hash_val >> 2
  if index < @table.size
    index
  else
    drop_first_bit(index)
  end
end

Make General -- Level

为了可以更灵活,我们引入 level 这个概念。

当对当前所有的 segments 都进行了一次 spit,则认为完成一轮 resizing,level 加 1.

依旧假设当前的 segment 为 2 个,当 grow 两次后,segment 变为 4,认为完成了一轮的 resizing,level 加 1。

当我们创建 hash table 的时候,为这个 table 创建一个 segment,并且设置 level 为 0。

hash_val 则变为

def hash_val(key)
  slots = 2.pow(@level + 1) * 4  # 当前可以表示的 segment 数目 * segment 内 bucket 的数量
  key % slots
end

segment_index 为

def segment_index(hash_val)
  segment_bit = Math.log @segment_size, 2
  index = hash_val >> segment_bit
  if index < @table.size
    index
  else
    # drop first bit
    index & (2.pow(@level) - 1)
  end
end

同时使用 @next_segment_index 记录将要被 split 的 segment 的 index。

def grow
  from_segment_index = @next_segment_index
  segment = @table[@next_segment_index]
  new_segment1, new_segment2 = split_segment(segment)

  @table[@next_segment_index] = new_segment1
  @table << new_segment2
  @next_segment_index += 1
end

Grow Condition

为了实现简单,每个 bucket 第一次出现 key hash val 冲突的时候,就认为需要做一次 resizing。

每次插入一对 key、val 之后,都检查一下,是否需要 resizing。


class Bucket
  def put(index, key, val)
    if @segment[index]
      @overflow_segment << [key, val]
      if !@overflowed
        @overflowed = true
        :need_grow
      end
    else
      @segment[index] = [key, val]
    end
  end
end

class Hash
  def put_segment(segment, bucket_index, key, val)
    @times_to_grow += 1 if :need_grow == segment.put(bucket_index, key, val)
  end

  def put(key, val)
    // xxxxx
    put_segment(segment, bucket_index, key, val)

    maybe_grow
  end

  def maybe_grow
    return if @times_to_grow == 0
    // xxxx
  end
end

完整代码: https://github.com/yfractal/concurrency-lab/blob/master/lib/linear_hash.rb

测试用例: https://github.com/yfractal/concurrency-lab/blob/master/spec/linear_hash_spec.rb

连接

关于散列表的一些思考

Berkeley CS186: Hash-based Indexes

hooopo 将本帖设为了精华贴。 01月27日 23:42
yfractal Erlang ETS Linear Hash Implementation 提及了此话题。 01月29日 21:34

@yfractal 哈哈,谢谢 Mike。

yfractal Linear Hash Revisit 提及了此话题。 02月20日 23:24
需要 登录 后方可回复, 如果你还没有账号请 注册新账号