shuffle

README

num-shuffle

将某段范围内的整数打乱

其数学表达为，对于y=encode(x),x=decode(y),x,y∈[min,max),且当x1!=x2时候，y1!=y2

快速开始

package main

import (
	"fmt"
	"github.com/RQZeng/num-shuffle"
)

func main() {
	numShuffle := shuffle.ShuffleType{}
	//对[1000,100000)范围内的整数做shuffle
	min, max := uint64(1000), uint64(100000)
	err := numShuffle.Init(min, max, "test")
	if err != nil {
		panic(err)
	}
	
	num := uint64(1001)
	//编码
	encodeNum, err := numShuffle.Encode(num)
	if err != nil {
		panic(err)
	}
	//解码
	decodeNum, err := numShuffle.Decode(encodeNum)
	if err != nil {
		panic(err)
	}
}

一些概念

• 二次幂数字：能用并且只能用二次幂表示的数字，比如1，2，4，8....等等，其分别为2的0,1,2,3次方
• 任意的数字，都可以用二次幂数字求和得到，比如100=64+32+4

原理

• skip32是一个将32为正整数打乱的算法，本算法不同于skip32,可以控制对某段范围内的整数做打乱
• 对于某范围内的整数空间的打乱，是利用加密算法里面普遍使用的异或来实现
• 具体做法
  • 先指定范围和密钥，初始化
    • 范围整数拆解为二次幂和的形式
    • 进行二进制幂的整数完美哈希组合
  • 编码
    • 判断要编码整数范围，使用以之对应的二进制幂完美哈希函数进行编码
  • 解码
    • 判断要编码整数范围，使用以之对应的二进制幂完美哈希函数进行解码
• 二次幂的完美哈希原理
• 指定范围的整数shuffle原理

对于同一个范围的整数，密钥不同的情况下，其编码解码出来的输出都是不一致的，外部难以猜测

适用场景

• 对于订单id，有内部外部id之分，内部和外部id可以相互转换，内部id希望可以递增以方便业务控制，外部id不希望有可被猜测的规则

一些限制

• 编码范围为uint64范围，即[0,0xFFFFFFFFFFFFFFFF),注意，其不包含0xFFFFFFFFFFFFFFFF这个数字的
• 由于整数需要分解为二进制幂和，是以其编码范围会有一个二进制幂范围层，举例
  • 对于[0,35),其最大值为1000=0b10_0011
  • 将会有3个二进制幂的完美哈希实例对应，分别为[0,1),[1,3),[4,35)
  • 0∈[0,1),是以其必定被映射到0
  • 2∈[1,3),是以其也会被映射到[1,3)范围内

Documentation

Index

• func FirstNoneZeroBit(n uint64) uint64
• func MurMurHash64(str string) (val uint64)
• func RevBit(val, num uint64) (revVal uint64)
• type NumMPHType
  • func (obj *NumMPHType) Decode(cipherNum uint64) (plainNum uint64, err error)
  • func (obj *NumMPHType) Encode(plainNum uint64) (cipherNum uint64, err error)
  • func (obj *NumMPHType) GetRange() (max uint64)
  • func (obj *NumMPHType) Init(max uint64, secretKey string)
  • func (obj *NumMPHType) String() string
• type ShuffleType
  • func (obj *ShuffleType) Decode(num uint64) (plainNum uint64, err error)
  • func (obj *ShuffleType) Encode(num uint64) (cipherNum uint64, err error)
  • func (obj *ShuffleType) ExtendDecode(num uint64) (plainNum uint64, err error)
  • func (obj *ShuffleType) ExtendEncode(num uint64) (cipherNum uint64, err error)
  • func (obj *ShuffleType) Init(min, max uint64, secretKey string) (err error)

Functions

func FirstNoneZeroBit

func FirstNoneZeroBit(n uint64) uint64

FirstNoneZeroBit 计算n的第一个二进制的1的下标值（小端序，从右往左,首位下标为1） 举例:

• n=0,其为0，是以没有下标为1 ==> ret=0
• n=0b0010_1010,其第一个1的下标值为6 ==> ret=6
• n=0b0101,其第一个1的下标值为3 ==> ret=3
• n=0xFFFF_FFFF_FFFF_FFFF,其第一个1的下标值为64 ==> ret=64

func MurMurHash64

func MurMurHash64(str string) (val uint64)

func RevBit

func RevBit(val, num uint64) (revVal uint64)

RevBit 反转二进制，val为想要反转的值，num为反转val几位 举例：

• val=0b1001,num=2 => revVal=0b1010 (从右数起，反转两位
• val=0b1011,num=3 => revVal=0b1110 (从右数起，反转三位
• val=0b1100_1011,num=5 => revVal=0b1101_1010

Types

type NumMPHType

type NumMPHType struct {
	// contains filtered or unexported fields
}

NumMPHType 完美哈希一段范围的整数（即将这段范围内的整数，做一个shuffle，由于数据空间太大，是以不能用类似52张扑克牌的方式做shuffle）

func (*NumMPHType) Decode

func (obj *NumMPHType) Decode(cipherNum uint64) (plainNum uint64, err error)

Encode 整数解密，输入密文整数，输出明文整数

func (*NumMPHType) Encode

func (obj *NumMPHType) Encode(plainNum uint64) (cipherNum uint64, err error)

Encode 整数加密，输入明文整数，输出密文整数

func (*NumMPHType) GetRange

func (obj *NumMPHType) GetRange() (max uint64)

GetRange 获取能完美hash的最大值 取值范围为[min,max),其为用户想要的取值范围，但是这里要打个折扣，取值范围将会是[min，2^(first_1_bit_idx_from_left-1))

func (*NumMPHType) Init

func (obj *NumMPHType) Init(max uint64, secretKey string)

Init 初始化 取值范围为[min,max),其为用户想 要的取值范围，但是这里要打个折扣，取值范围将会是[min，2^(first_1_bit_idx_from_left-1))

func (*NumMPHType) String

func (obj *NumMPHType) String() string

String ...

type ShuffleType

type ShuffleType struct {
	// contains filtered or unexported fields
}

func (*ShuffleType) Decode

func (obj *ShuffleType) Decode(num uint64) (plainNum uint64, err error)

Encode 解码，num范围必须在Init中[min,max)之内

func (*ShuffleType) Encode

func (obj *ShuffleType) Encode(num uint64) (cipherNum uint64, err error)

Encode 编码，num范围必须在Init中[min,max)之内

func (*ShuffleType) ExtendDecode

func (obj *ShuffleType) ExtendDecode(num uint64) (plainNum uint64, err error)

func (*ShuffleType) ExtendEncode

func (obj *ShuffleType) ExtendEncode(num uint64) (cipherNum uint64, err error)

func (*ShuffleType) Init

func (obj *ShuffleType) Init(min, max uint64, secretKey string) (err error)

Init 初始化，范围为[min,max)