Time33算法

15 Feb 2019

1. time33

Time33是字符串哈希函数，现在几乎所有流行的HashMap都采用了DJB Hash Function，俗称“Times33”算法。Times33的算法很简单，就是不断的乘33。

c语言版本

#include "stdio.h"

unsigned int time33(char *);
int main(){
    char str[3] = "c语言";
   int res;
    
    res = time33(str);
    printf("%d", res);
}

/**
* time33算法
*/
unsigned int time33(char *str){
    unsigned int hash = 5381;
    while(*str){
        hash += (hash << 5 ) + (*str++);
    }
    return (hash & 0x7FFFFFFF);
} JAVA版本

public String time33(String skey) {
        if (skey == null) return null;
        int hash = 5381;
        for (int i = 0, len = skey.length(); i < len; ++i) {
            int cc = skey.charAt(i);
            hash += (hash << 5) + cc;
        }
        hash &= 0x7fffffff;
        return String.valueOf(hash);
    } Javascript版本

//哈希time33算法
function time33(str){
    for(var i = 0, len = str.length,hash = 5381; i < len; ++i){
       hash += (hash << 5) + str.charAt(i).charCodeAt();
    };
    return hash & 0x7fffffff;
};

为什么初始值是5381？

5381（001 010 100 000 101），据说hash后的分布更好一些。

2. python中的字符数字之间的转换函数

int(x [,base ])         将x转换为一个整数    
long(x [,base ])        将x转换为一个长整数    
float(x )               将x转换到一个浮点数    
complex(real [,imag ])  创建一个复数    
str(x )                 将对象 x 转换为字符串    
repr(x )                将对象 x 转换为表达式字符串    
eval(str )              用来计算在字符串中的有效Python表达式,并返回一个对象    
tuple(s )               将序列 s 转换为一个元组    
list(s )                将序列 s 转换为一个列表    
chr(x )                 将一个整数转换为一个字符    
unichr(x )              将一个整数转换为Unicode字符    
ord(x )                 将一个字符转换为它的整数值    
hex(x )                 将一个整数转换为一个十六进制字符串    
oct(x )                 将一个整数转换为一个八进制字符串   

chr(65)=’A’ ord(‘A’)=65

int(‘2’)=2; str(2)=’2’

def time33(string):
    hash = 5381
    for char in string:
        hash = ord(char)* 33 + hash + ord(char)
    return  hash

print(time33("hash"))

3. 快排算法

了解了下快排算法，原理：

一趟排序：找一个数，将小于等于它的，放在它左边，大于它的放在它右边。
终止：对左边的和右边的分别用上面的方法排序，至到左边或右边只有一个数为止。

我的理解，划分为小单元，至到划分到一个数为一个单元为止。大化小，分别排序。

PYTHON版本：

	def quickSort(list):
	    if len(list)<2:
	        return list
	    base = list[0]
	    left = [x for x in list[1:] if x<= base]
	    right = [x for x in list[1:] if x>base]
	    return  quickSort(left) + [base] + quickSort(right)
	
	print(quickSort([100,24,56,78,34,56,33,23,78,99]))

结果：[23, 24, 33, 34, 56, 56, 78, 78, 99, 100]

python 代码很简单明白。

参考：