# Google Maglev Hashing实现

Damon_330b · · 408 次点击 · · 开始浏览

#### 原理说明

Maglev Hashing的基本思想是为每一个节点生成一个优先填充表，列表的值就是该节点想要填充查询表的位置.
lookup table

#### 算法实现

`M`为查询表的大小。对与每一个节点`i``permutation[i]`为优先填充表，`permutation[i]`的取值是数组`[0, M-1]`的一个随机顺序排列，`permutation`是一个二维数组。

``````func Hash1(k int) int {
s := uint64(2654435769)
p := uint32(14)
tmp := (s * uint64(k)) % (1 << 32)
return int(tmp / (1 << (32 - p)))
}

func Hash2(k int) int {
s := uint64(1654435769)
p := uint32(14)
tmp := (s * uint64(k)) % (1 << 32)
return int(tmp / (1 << (32 - p)))
}
``````

``````offset←h1(name[i]) mod M
skip←h2(name[i]) mod (M−1)+1
``````

`permutation[ i ][ j ]←(offset+ j×skip) mod M 0<=j<= M-1`

``````func isPrime(n int) bool {
if n < 2 {
return false
}
end := int(math.Sqrt(float64(n)))
for i := 2; i <= end; i++ {
if n%i == 0 {
return false
}
}
return true
}

func findPrime(n int) int {
//始终有大于n的质数
for {
if isPrime(n) {
return n
}
n++
}
}
``````

``````type MaglevHash struct {
m, n        int
permutation [][]int
entry       []int
nodeState   []bool
}

func NewMaglevHash(n int) *MaglevHash {
m := findPrime(5 * n)
permutation := make([][]int, n)
entry := make([]int, m)
nodeState := make([]bool, n)
for idx, _ := range nodeState {
nodeState[idx] = true
}

return &MaglevHash{
m:           m,
n:           n,
permutation: permutation,
entry:       entry,
nodeState:   nodeState,
}
}
``````

``````func (mh *MaglevHash) Permutate() {
for idx, _ := range mh.permutation {
mh.permutation[idx] = make([]int, mh.m)
}
for i := 0; i < mh.n; i++ {
offset := Hash1(i+1) % mh.m
skip := Hash2(i+1)%(mh.m-1) + 1
for j := 0; j < mh.m; j++ {
mh.permutation[i][j] = (offset + j*skip) % mh.m
}
}
}
``````

``````func (mh *MaglevHash) Populate() {
for idx, _ := range mh.entry {
mh.entry[idx] = -1
}
next := make([]int, mh.n)
n := 0
for {
for i := 0; i < mh.n; i++ {
if !mh.nodeState[i] {
continue
}
c := mh.permutation[i][next[i]]
for mh.entry[c] >= 0 {
next[i]++
c = mh.permutation[i][next[i]]
}
mh.entry[c] = i
next[i]++
n++
if n == mh.m {
return
}
}
}
}
``````

``````func (mh *MaglevHash) DownNode(idx int) error {
if idx > mh.n-1 {
return errors.New("invalid idx")
}
mh.nodeState[idx] = false
return nil
}
``````

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

#### 原理说明

Maglev Hashing的基本思想是为每一个节点生成一个优先填充表，列表的值就是该节点想要填充查询表的位置.
lookup table

#### 算法实现

`M`为查询表的大小。对与每一个节点`i``permutation[i]`为优先填充表，`permutation[i]`的取值是数组`[0, M-1]`的一个随机顺序排列，`permutation`是一个二维数组。

``````func Hash1(k int) int {
s := uint64(2654435769)
p := uint32(14)
tmp := (s * uint64(k)) % (1 << 32)
return int(tmp / (1 << (32 - p)))
}

func Hash2(k int) int {
s := uint64(1654435769)
p := uint32(14)
tmp := (s * uint64(k)) % (1 << 32)
return int(tmp / (1 << (32 - p)))
}
``````

``````offset←h1(name[i]) mod M
skip←h2(name[i]) mod (M−1)+1
``````

`permutation[ i ][ j ]←(offset+ j×skip) mod M 0<=j<= M-1`

``````func isPrime(n int) bool {
if n < 2 {
return false
}
end := int(math.Sqrt(float64(n)))
for i := 2; i <= end; i++ {
if n%i == 0 {
return false
}
}
return true
}

func findPrime(n int) int {
//始终有大于n的质数
for {
if isPrime(n) {
return n
}
n++
}
}
``````

``````type MaglevHash struct {
m, n        int
permutation [][]int
entry       []int
nodeState   []bool
}

func NewMaglevHash(n int) *MaglevHash {
m := findPrime(5 * n)
permutation := make([][]int, n)
entry := make([]int, m)
nodeState := make([]bool, n)
for idx, _ := range nodeState {
nodeState[idx] = true
}

return &MaglevHash{
m:           m,
n:           n,
permutation: permutation,
entry:       entry,
nodeState:   nodeState,
}
}
``````

``````func (mh *MaglevHash) Permutate() {
for idx, _ := range mh.permutation {
mh.permutation[idx] = make([]int, mh.m)
}
for i := 0; i < mh.n; i++ {
offset := Hash1(i+1) % mh.m
skip := Hash2(i+1)%(mh.m-1) + 1
for j := 0; j < mh.m; j++ {
mh.permutation[i][j] = (offset + j*skip) % mh.m
}
}
}
``````

``````func (mh *MaglevHash) Populate() {
for idx, _ := range mh.entry {
mh.entry[idx] = -1
}
next := make([]int, mh.n)
n := 0
for {
for i := 0; i < mh.n; i++ {
if !mh.nodeState[i] {
continue
}
c := mh.permutation[i][next[i]]
for mh.entry[c] >= 0 {
next[i]++
c = mh.permutation[i][next[i]]
}
mh.entry[c] = i
next[i]++
n++
if n == mh.m {
return
}
}
}
}
``````

``````func (mh *MaglevHash) DownNode(idx int) error {
if idx > mh.n-1 {
return errors.New("invalid idx")
}
mh.nodeState[idx] = false
return nil
}
``````