烦死个人了
范文一：hash冲突
/*
* hashquad.c 开放定址法解决hash 冲突问题
*/
#include #include #include "hashquad.h" #include "fatal.h" #define MIN_TABLE_SIZE (10) #define REHASH_FACTOR (0.7) enum kind_of_entry { legitimate, empty, deleted }; struct hash_entry { element_type element; enum kind_of_entry info; }; typedef struct hash_entry cell; struct hash_tbl { int table_size; /* 表容量 */ int entry_cnt; /* 已填入的单元数量 */ cell *cells; }; static int need_rehash( hash_table h ) { return ( h->entry_cnt > h->table_size * REHASH_FACTOR ); } static int next_prime( int N ) { int i; if ( N % 2 == 0 ) N++; for ( ; ; N += 2 ){ for ( i = 3; i * i <= n;="" i="" +="2"> if ( N % i == 0 ) goto cont_outer; } return N; cont_outer: ; } } static Index hash( element_type key, int table_size ) { return key % table_size; } static hash_table initialize_table( int table_size ) { hash_table h; int i; if ( table_size < min_table_size=""> Error("Table size too small!"); h = malloc( sizeof( struct hash_tbl ) ); if ( h == NULL ) Error("Out of space!"); h->table_size = next_prime( table_size ); h->cells = malloc( sizeof( cell ) * h->table_size ); if ( h->cells == NULL ){ free( h ); Error("Out of space!"); } for ( i = 0; i < h-="">table_size; i++){ h->cells[ i ].info = empty; } h->entry_cnt = 0; return h; } static Pos find( element_type key, hash_table h ) { Pos cur_pos; int collision_num; collision_num = 0; cur_pos = hash( key, h->table_size ); /* 当hash 表大部分被占满，这个过程可能很慢。 也有可能进入死循环! 需要在适当的时候进行rehash! */ while ( h->cells[ cur_pos ].info != empty && h->cells[ cur_pos ].element != key ){ cur_pos += 2 * ++collision_num - 1; if ( cur_pos >= h->table_size ) cur_pos -= h->table_size; } return cur_pos; } static void insert( element_type key, hash_table h ) { Pos p; p = find( key, h ); if ( h->cells[ p ].info != legitimate ){ h->cells[ p ].info = legitimate; h->cells[ p ].element = key; h->entry_cnt++; } } static hash_table rehash( hash_table h) { int i, old_size; cell *old_cells; old_cells = h->cells; old_size = h->table_size; /* 创建一个新的double size 的空表 */ h = initialize_table( 2 * old_size ); /* 拷贝旧表的数据到新表 */ for ( i = 0; i < old_size;="" i++=""> if ( old_cells[ i ].info == legitimate ) insert( old_cells[ i ].element, h ); } free( old_cells ); return h; } /************ The next is test functions ***************/ #define get_array_size(array) ( sizeof(array) / sizeof(array[0]) ) void test_hashquad( void ) { int i; Pos p; hash_table h; element_type datas[100]; for ( i = 0; i < get_array_size(="" datas="" );="" i++=""> datas[i] = rand() % 1000; } h = initialize_table( 13 ); if ( h == NULL ) Error("Initialize error!"); for ( i = 0; i < get_array_size(="" datas="" );="" i++=""> insert( datas[i], h ); /* 在每次插入操作后检查是否需要rehash */ if ( need_rehash( h ) ) h = rehash( h ); } p = find( 67, h ); if ( h->cells[p].info != legitimate ){ printf("\n\t key value 67 not in hash table!\n"); }else{ printf("\n\t key value 67 in hash table!\n"); } p = find( datas[31], h ); if ( h->cells[p].info != legitimate ){ printf("\n\t key value %d not in hash table!\n",datas[31]); }else{ printf("\n\t key value %d in hash table!\n",datas[31]); } i = i; return; } /*********************************************************************************************************/ /* hashquad.h */ #ifndef _HASHQUAD_H_ #define _HASHQUAD_H_ typedef int element_type; typedef unsigned int Index; typedef Index Pos; struct hash_tbl; typedef struct hash_tbl *hash_table; #endif 这是一个将整数的质因数分解算法： #include #include #include { bool flag; for (int i = int(sqrt((double)num));i>1;i--) { if((num%i)==0) flag= false; } if(!flag) { for (int i = int(sqrt(num));i>1;i--) { if((num%i)==0) { f(i); num = num/i; f(num); break; } } } else printf("%d\t",num); } int main() { int num; printf("please input a number:"); scanf("%d",&num); f(num); return 0; } 加颜色的部分为核心算法的C 语言表述。 1、选择合适的算法和数据结构 应该熟悉算法语言，知道各种算法的优缺点，具体资料请参见相应的参考资料，有很多计算机书籍上都有介绍。将比较慢的顺序查找法用较快的二分查找或乱序查找法代替，插入排序或冒泡排序法用快速排序、合并排序或根排序代替，都可以大大提高程序执行的效率。. 选择一种合适的数据结构也很重要，比如你在一堆随机存放的数中使用了大量的插入和删除指令，那使用链表要快得多。数组与指针语句具有十分紧密的关系，一般来说，指针比较灵活简洁，而数组则比较直观，容易理解。对于大部分的编译器，使用指针比使用数组生成的代码更短，执行效率更高。但是在Keil 中则相反， 使用数组比使用的指针生成的代码更短。。 2、使用尽量小的数据类型 能够使用字符型(char)定义的变量，就不要使用整型(int)变量来定义；能够使用整型变量定义的变量就不要用长整型(long int) ，能不使用浮点型(float)变量就不要使用浮点型变量。当然，在定义变量后不要超过变量的作用范围，如果超过变量的范围赋值，C 编译器并不报错，但程序运行结果却错了，而且这样的错误很难发现。 在ICCAVR 中，可以在Options 中设定使用printf 参数，尽量使用基本型参数(%c、%d、%x、%X 、%u和%s格式说明符) ，少用长整型参数(%ld、%lu、%lx和%lX格式说明符) ，至于浮点型的参数(%f)则尽量不要使用，其它C 编译器也一样。在其它条件不变的情况下，使用%f参数，会使生成的代码的数量增加很多，执行速度降低。 3、使用自加、自减指令 通常使用自加、自减指令和复合赋值表达式(如a-=1及a+=1等) 都能够生成高质量的程序代码，编译器通常都能够生成inc 和dec 之类的指令，而使用 a=a+1或a=a-1之类的指令，有很多C 编译器都会生成二到三个字节的指令。在AVR 单片适用的ICCAVR 、GCCAVR 、IAR 等C 编译器以上几种书写方式生成的代码是一样的，也能够生成高质量的inc 和dec 之类的的代码。 4、减少运算的强度 可以使用运算量小但功能相同的表达式替换原来复杂的的表达式。如下： (1)、求余运算。 a=a%8; 可以改为： a=a&7; 说明：位操作只需一个指令周期即可完成，而大部分的C 编译器的“%”运算均是调用子程序来完成，代码长、执行速度慢。通常，只要求是求2n 方的余数，均可使用位操作的方法来代替。 (2)、平方运算 a=pow(a,2.0); 可以改为： a=a*a; 说明：在有内置硬件乘法器的单片机中(如51系列) ，乘法运算比求平方运算快得多，因为浮点数的求平方是通过调用子程序来实现的，在自带硬件乘法器的AVR 单片机中，如ATMega163中，乘法运算只需2个时钟周期就可以完成。既使是在没有内置硬件乘法器的AVR 单片机中，乘法运算的子程序比平方运算的子程序代码短，执行速度快。 如果是求3次方，如： a=pow(a,3.0); 更改为： a=a*a*a； 则效率的改善更明显。 (3)、用移位实现乘除法运算 a=a*4; b=b/4; 可以改为： a=a<> b=b>>2; 说明：通常如果需要乘以或除以2n ，都可以用移位的方法代替。在ICCAVR 中，如果乘以2n ，都可以生成左移的代码，而乘以其它的整数或除以任何数，均调用乘除法子程序。用移位的方法得到代码比调用乘除法子程序生成的代码效率高。实际上，只要是乘以或除以一个整数，均可以用移位的方法得到结果，如： a=a*9 可以改为： a=(a<> 5、循环 (1)、循环语 对于一些不需要循环变量参加运算的任务可以把它们放到循环外面，这里的任务包括表达式、函数的调用、指针运算、数组访问等，应该将没有必要执行多次的操作全部集合在一起，放到一个i nit 的初始化程序中进行。 (2)、延时函数： 通常使用的延时函数均采用自加的形式： void delay (void) { unsigned int i; for (i=0;i<> ; } 将其改为自减延时函数： void delay (void) { unsigned int i; for (i=1000;i>0;i--) ; } 两个函数的延时效果相似，但几乎所有的C 编译对后一种函数生成的代码均比前一种代码少1~3个字节，因为几乎所有的MCU 均有为0转移的指令，采用后一种方式能够生成这类指令。在使用while 循环时也一样，使用自减指令控制循环会比使用自加指令控制循环生成的代码更少1~3个字母。但是在循环中有通过循环变量“i”读写数组的指令时，使用预减循环时有可能使数组超界，要引起注意。 (3)while循环和do…while循环 用while 循环时有以下两种循环形式： unsigned int i; i=0; while (i<> { i++; //用户程序 } 或： unsigned int i; i=1000; do i--; //用户程序 while (i>0); 在这两种循环中，使用do…while循环编译后生成的代码的长度短于while 循环。 6、查表 在程序中一般不进行非常复杂的运算，如浮点数的乘除及开方等，以及一些复杂的数学模型的插补运算，对这些即消耗时间又消费资源的运算，应尽量使用查表的方式，并且将数据表置于程序存储区。如果直接生成所需的表比较困难，也尽量在启了，减少了程序执行过程中重复计算的工作量。 7、其它 比如使用在线汇编及将字符串和一些常量保存在程序存储器中，均有利于优化。 enum类型的本质 至从C 语言开始enum 类型就被作为用户自定义分类有限集合常量的方法被引入到了语言 当中，而且一度成为C++中定义编译期常量的唯一方法（后来在类中引入了静态整型常量）。 根据上面对enum 类型的描述，到底enum 所定义出来的类型是一个什么样的类型呢？作为 一个用户自定义的类型其所占用的内存空间是多少呢？使用enum 类型是否真的能够起到有限 集合常量的边界约束呢？大家可能都知道enum 类型和int 类型具有隐示（自动）转换的规则， 那么是否真的在任何地方都可以使用enum 类型的变量来代替int 类型的变量呢？下面会逐一 回答这些问题。 1. 到底enum 所定义出来的类型是一个什么样的类型呢？ 在C++中大家都知道仅仅有两种大的类型分类：POD 类型和类类型（不清楚的可以参 见我的其他文章）。enum 所定义的类型其实属于POD 类型，也就是说它会参与到POD 类型的隐示转换规则当中去，所以才会出现enum 类型与int 类型之间的隐示转换现象。 那么也就是说enum 所定义的类型不具备名字空间限定能力（因为不属于类类型）， 其所定义的常量子具备和enum 类型所在名字空间相同的可见性，由于自身没有名字 限定能力，所以会出现名字冲突现象。如： struct CEType { enum EType1 { e1, e2 }; enum EType2 { e1, e2 }; }; 上面的例子会出现e1、e2名字冲突编译时错误，原因就在于枚举子（e1、e2）是 CEType 名字空间中的名字，同样在引用该CEType 中的枚举子时必须采用CEType::e1 这样的方式进行，而不是CEType::EType1::e1来进行引用。 2. 作为一个用户自定义的类型其所占用的内存空间是多少呢？ 该问题就是sizeof( EType1 ) 等于多少的问题，是不是每一个用户自定义的枚举类 型都具有相同的尺寸呢？在大多数的32位编译器下（如：VC++、gcc 等）一个枚举类 型的尺寸其实就是一个sizeof( int ) 的大小，难道枚举类型的尺寸真的就应该是int 类型的尺寸吗？其实不是这样的，在C++标准文档（ISO14882）中并没有这样来定义， 标准中是这样说明的：“枚举类型的尺寸是以能够容纳最大枚举子的值的整数的尺寸”， 同时标准中也说名了：“枚举类型中的枚举子的值必须要能够用一个int 类型表述”， 也就是说，枚举类型的尺寸不能够超过int 类型的尺寸，但是是不是必须和int 类型 具有相同的尺寸呢？上面的标准已经说得很清楚了，只要能够容纳最大的枚举子的 值的整数就可以了，那么就是说可以是char 、short 和int 。例如： enum EType1 { e1 = CHAR_MAX }; enum EType2 { e2 = SHRT_MAX }; enum EType3 { e3 = INT_MAX }; 上面的三个枚举类型分别可以用char 、short 、int 的内存空间进行表示，也就是： sizeof( EType1 ) == sizeof( char ); sizeof( EType2 ) == sizeof( short ); sizeof( EType3 ) == sizeof( int ); 那为什么在32位的编译器下都会将上面三个枚举类型的尺寸编译成int 类型的尺寸呢？ 主要是从32位数据内存对其方面的要求进行考虑的，在某些计算机硬件环境下具有对 齐的强制性要求（如：sun SPARC ），有些则是因为采用一个完整的32位字长CPU 处理 效率非常高的原因（如：IA32）。所以不可以简单的假设枚举类型的尺寸就是int 类 型的尺寸，说不定会遇到一个编译器为了节约内存而采用上面的处理策略。 3. 使用enum 类型是否真的能够起到有限集合常量的边界约束呢？ 首先看一下下面这个例子： enum EType { e1 = 0, e2 }; void func1( EType e ) { if ( e == e1 ) { // do something } // do something because e != e1 must e == e2 } void func2( EType e ) { if ( e == e1 ) { // do something } else if ( e == e2 ) { // do something } } func1( static_cast func2( static_cast 上面的代码应该很清楚的说明了这样一种异常的情况了，在使用一个操出范围的整 型值调用func1函数时会导致函数采取不该采取的行为，而第二个函数可能会好一些 他仅仅是忽略了超出范围的值。这就说明枚举所定义的类型并不是一个真正强类型 的有限常量集合，这样一种条件下和将上述的两个函数参数声明成为整数类型没有 任何差异。所以以后要注意标准定义中枚举类型的陷阱。（其实只有类类型才是真 正的强类型） 4. 是否真的在任何地方都可以使用enum 类型的变量来代替int 类型的变量呢？ 通过上面的讨论，其实枚举类型的变量和整型变量具有了太多的一致性和可互换性， 那么是不是在每一个可以使用int 类型的地方都可以很好的用枚举类型来替代呢？ 其实也不是这样的，毕竟枚举类型是一个在编译时可区分的类型，同时第2点的分析 枚举类型不一定和int 类型具有相同的尺寸，这两个差异就决定了在某些场合是不可 以使用枚举类型来代替int 类型的。如： 第一种情况： enum EType { e1 = 0, e2, e3 }; EType val; std::cin >> val; 第二种情况： enum EType { e1 = 0, e2, e3 }; EType val; std::scanf( "%d", &val ); 上面的两种情况看是基本上属于同一种类型的问题，其实不然。第一种情况会导致 编译时错误，会因为std::cin没有定义对应的枚举类型的重载>>运算符而出错，这 就说明枚举类型是一种独立和鉴别的类型；而第二种情况不会有任何编译时问题， 但是可能会导致scanf 函数栈被破坏而使得程序运行非法，为什么会这样呢？上面 已经分析过了枚举类型变量的尺寸不一定和int 类型相同，这样一来我们采用%d就 是说将枚举类型变量val 当作4字节的int 变量来看待并进行参数压栈，而在某些编 译器下sizeof( val ) 等于1字节，这样scanf 函数就会将val 变量地址中的后续的三 字节地址也压入栈中，并对其进行赋值，也许val 变量后续的三个字节的地址没有 特殊含义可以被改写（比如是字节对齐的空地址空间），可能会认为他不会出现错 误，其实不然，在scanf 函数调用结束后会进行栈清理，这样一来会导致scanf 函数 清理了过多的地址空间，从而破坏了外围函数的栈指针的指向，从而必然会导致程 序运行时错误。 由上面的说明枚举类型有那么多的缺点，那我们怎样才能够有一个类型安全的枚举类型 呢？其实可以采用类类型来模拟枚举类型的有限常量集合的概念，同时得到类型安全的好处， 具体参见后续的文章。 文章转自：http://www.cppblog.com/chemz/archive/2007/06/05/25578.html 函数名: stpcpy 功 能: 拷贝一个字符串到另一个 用 法: char *stpcpy(char *destin, char *source); 程序例: #include #include int main(void) { char string[10]; char *str1 = "abcdefghi"; stpcpy(string, str1); printf("%s\n", string); return 0; } 函数名: strcat 功 能: 字符串拼接函数 用 法: char *strcat(char *destin, char *source); 程序例: #include #include int main(void) { char destination[25]; char *blank = " ", *c = "C++", *Borland = "Borland"; strcpy(destination, Borland); strcat(destination, blank); strcat(destination, c); printf("%s\n", destination); return 0; } 函数名: strchr 功 能: 在一个串中查找给定字符的第一个匹配之处\ 用 法: char *strchr(char *str, char c); 程序例: #include #include { char string[15]; char *ptr, c = 'r'; strcpy(string, "This is a string"); ptr = strchr(string, c); if (ptr) printf("The character %c is at position: %d\n", c, ptr-string); else printf("The character was not found\n"); return 0; } 函数名: strcmp 功 能: 串比较 用 法: int strcmp(char *str1, char *str2); 看Asic 码，str1>str2，返回值 > 0；两串相等，返回0 程序例: #include #include { char *buf1 = "aaa", *buf2 = "bbb", *buf3 = "ccc"; int ptr; ptr = strcmp(buf2, buf1); if (ptr > 0) printf("buffer 2 is greater than buffer 1\n"); else printf("buffer 2 is less than buffer 1\n"); ptr = strcmp(buf2, buf3); if (ptr > 0) printf("buffer 2 is greater than buffer 3\n"); else printf("buffer 2 is less than buffer 3\n"); return 0; } 函数名: strncmpi 功 能: 将一个串中的一部分与另一个串比较, 不管大小写 用 法: int strncmpi(char *str1, char *str2, unsigned maxlen); 程序例: #include #include int main(void) { char *buf1 = "BBB", *buf2 = "bbb"; int ptr; ptr = strcmpi(buf2, buf1); if (ptr > 0) printf("buffer 2 is greater than buffer 1\n"); if (ptr <> printf("buffer 2 is less than buffer 1\n"); if (ptr == 0) printf("buffer 2 equals buffer 1\n"); return 0; } 函数名: strcpy 功 能: 串拷贝 用 法: char *strcpy(char *str1, char *str2); 程序例: #include #include int main(void) { char string[10]; char *str1 = "abcdefghi"; strcpy(string, str1); printf("%s\n", string); return 0; } 函数名: strcspn 功 能: 在串中查找第一个给定字符集内容的段 用 法: int strcspn(char *str1, char *str2); 程序例: #include #include #include int main(void) { char *string1 = "1234567890"; char *string2 = "747DC8"; int length; length = strcspn(string1, string2); printf("Character where strings intersect is at position %d\n", length); return 0; } 函数名: strdup 功 能: 将串拷贝到新建的位置处 用 法: char *strdup(char *str); 程序例: #include #include #include int main(void) { char *dup_str, *string = "abcde"; dup_str = strdup(string); printf("%s\n", dup_str); free(dup_str); return 0; } 函数名: stricmp 功 能: 以大小写不敏感方式比较两个串 用 法: int stricmp(char *str1, char *str2); 程序例: #include #include int main(void) { char *buf1 = "BBB", *buf2 = "bbb"; int ptr; ptr = stricmp(buf2, buf1); if (ptr > 0) printf("buffer 2 is greater than buffer 1\n"); if (ptr <> printf("buffer 2 is less than buffer 1\n"); if (ptr == 0) printf("buffer 2 equals buffer 1\n"); return 0; } 函数名: strerror 功 能: 返回指向错误信息字符串的指针 用 法: char *strerror(int errnum); 程序例: #include #include int main(void) { char *buffer; buffer = strerror(errno); printf("Error: %s\n", buffer); return 0; } 函数名: strcmpi 功 能: 将一个串与另一个比较, 不管大小写 用 法: int strcmpi(char *str1, char *str2); 程序例: #include #include int main(void) { char *buf1 = "BBB", *buf2 = "bbb"; int ptr; ptr = strcmpi(buf2, buf1); if (ptr > 0) printf("buffer 2 is greater than buffer 1\n"); if (ptr <> printf("buffer 2 is less than buffer 1\n"); if (ptr == 0) printf("buffer 2 equals buffer 1\n"); return 0; } 函数名: strncmp 功 能: 串比较 用 法: int strncmp(char *str1, char *str2, int maxlen); 程序例: #include #include int main(void) { char *buf1 = "aaabbb", *buf2 = "bbbccc", *buf3 = "ccc"; int ptr; ptr = strncmp(buf2,buf1,3); if (ptr > 0) printf("buffer 2 is greater than buffer 1\n"); else printf("buffer 2 is less than buffer 1\n"); ptr = strncmp(buf2,buf3,3); if (ptr > 0) printf("buffer 2 is greater than buffer 3\n"); else printf("buffer 2 is less than buffer 3\n"); return(0); } 函数名: strncmpi 功 能: 把串中的一部分与另一串中的一部分比较, 不管大小写 用 法: int strncmpi(char *str1, char *str2); 程序例: #include #include int main(void) { char *buf1 = "BBBccc", *buf2 = "bbbccc"; int ptr; ptr = strncmpi(buf2,buf1,3); if (ptr > 0) printf("buffer 2 is greater than buffer 1\n"); if (ptr <> printf("buffer 2 is less than buffer 1\n"); if (ptr == 0) printf("buffer 2 equals buffer 1\n"); return 0; } 函数名: strncpy 功 能: 串拷贝 用 法: char *strncpy(char *destin, char *source, int maxlen); 程序例: #include #include int main(void) { char string[10]; char *str1 = "abcdefghi"; strncpy(string, str1, 3); string[3] = '\0'; printf("%s\n", string); return 0; } 函数名: strnicmp 功 能: 不注重大小写地比较两个串 用 法: int strnicmp(char *str1, char *str2, unsigned maxlen); 程序例: #include #include int main(void) { char *buf1 = "BBBccc", *buf2 = "bbbccc"; int ptr; ptr = strnicmp(buf2, buf1, 3); if (ptr > 0) printf("buffer 2 is greater than buffer 1\n"); if (ptr <> printf("buffer 2 is less than buffer 1\n"); if (ptr == 0) printf("buffer 2 equals buffer 1\n"); return 0; } 函数名: strnset 功 能: 将一个串中的所有字符都设为指定字符 用 法: char *strnset(char *str, char ch, unsigned n); 程序例: #include #include int main(void) { char *string = "abcdefghijklmnopqrstuvwxyz"; char letter = 'x'; printf("string before strnset: %s\n", string); strnset(string, letter, 13); printf("string after strnset: %s\n", string); return 0; } 函数名: strpbrk 功 能: 在串中查找给定字符集中的字符 用 法: char *strpbrk(char *str1, char *str2); 程序例: #include #include int main(void) { char *string1 = "abcdefghijklmnopqrstuvwxyz"; char *string2 = "onm"; char *ptr; ptr = strpbrk(string1, string2); if (ptr) printf("strpbrk found first character: %c\n", *ptr); else printf("strpbrk didn't find character in set\n"); return 0; } 函数名: strrchr 功 能: 在串中查找指定字符的最后一个出现 用 法: char *strrchr(char *str, char c); 程序例: #include #include int main(void) { char string[15]; char *ptr, c = 'r'; strcpy(string, "This is a string"); ptr = strrchr(string, c); if (ptr) printf("The character %c is at position: %d\n", c, ptr-string); else printf("The character was not found\n"); return 0; } 函数名: strrev 功 能: 串倒转 用 法: char *strrev(char *str); 程序例: #include #include int main(void) { char *forward = "string"; printf("Before strrev(): %s\n", forward); strrev(forward); printf("After strrev(): %s\n", forward); return 0; } 函数名: strset 功 能: 将一个串中的所有字符都设为指定字符 用 法: char *strset(char *str, char c); 程序例: #include #include int main(void) { char string[10] = "123456789"; char symbol = 'c'; printf("Before strset(): %s\n", string); strset(string, symbol); printf("After strset(): %s\n", string); return 0; } 函数名: strspn 功 能: 在串中查找指定字符集的子集的第一次出现 用 法: int strspn(char *str1, char *str2); 程序例: #include #include #include int main(void) { char *string1 = "1234567890"; char *string2 = "123DC8"; int length; length = strspn(string1, string2); printf("Character where strings differ is at position %d\n", length); return 0; } 函数名: strstr 功 能: 在串中查找指定字符串的第一次出现 用 法: char *strstr(char *str1, char *str2); 程序例: #include #include int main(void) { char *str1 = "Borland International", *str2 = "nation", *ptr; ptr = strstr(str1, str2); printf("The substring is: %s\n", ptr); return 0; } 函数名: strtod 功 能: 将字符串转换为double 型值 用 法: double strtod(char *str, char **endptr); 程序例: #include #include int main(void) { char input[80], *endptr; double value; printf("Enter a floating point number:"); gets(input); value = strtod(input, &endptr); printf("The string is %s the number is %lf\n", input, value); return 0; } 函数名: strtok 功 能: 查找由在第二个串中指定的分界符分隔开的单词 用 法: char *strtok(char *str1, char *str2); 程序例: #include #include int main(void) { char input[16] = "abc,d"; char *p; /* strtok places a NULL terminator in front of the token, if found */ p = strtok(input, ","); if (p) printf("%s\n", p); /* A second call to strtok using a NULL as the first parameter returns a pointer to the character following the token */ p = strtok(NULL, ","); if (p) printf("%s\n", p); return 0; } 函数名: strtol 功 能: 将串转换为长整数 用 法: long strtol(char *str, char **endptr, int base); 程序例: #include #include int main(void) { char *string = "87654321", *endptr; long lnumber; /* strtol converts string to long integer */ lnumber = strtol(string, &endptr, 10); printf("string = %s long = %ld\n", string, lnumber); return 0; } 函数名: strupr 功 能: 将串中的小写字母转换为大写字母 用 法: char *strupr(char *str); 程序例: #include #include int main(void) { char *string = "abcdefghijklmnopqrstuvwxyz", *ptr; /* converts string to upper case characters */ ptr = strupr(string); printf("%s\n", ptr); return 0; } 函数名: swab 功 能: 交换字节 用 法: void swab (char *from, char *to, int nbytes); 程序例: #include #include #include char source[15] = "rFna koBlrna d"; char target[15]; int main(void) { swab(source, target, strlen(source)); printf("This is target: %s\n", target); return 0; } HashMap 实现原理分析 标签:HashMap 2013-11-05 15:23102443人阅读 评论 (49) 收藏举报 分类: 【 Java SE】(32) 版权声明:本文为博主原创文章,未经博主允许不得转载。 目录 (?)[+] 1. HashMap的数据结构 数据结构 中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。 数组 数组存储区间是连续的, 占用内存严重, 故空间复杂的很大。 但数组的二分查找时间复杂度 小,为 O(1); 数组的特点是:寻址容易,插入和删除困难 ; 链表 链表存储区间离散, 占用内存比较宽松, 故空间复杂度很小, 但时间复杂度很大, 达 O (N ) 。 链表 的特点是:寻址困难,插入和删除容易。 哈希表 那么我们能不能综合两者的特性, 做出一种寻址容易, 插入删除也容易的数据结构?答案是 肯定的,这就是我们要提起的哈希表。 哈希表((Hash table)既满足了数据的查找方便, 同时不占用太多的内容空间,使用也十分方便。 哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法 —— 拉链法 ,我 们可以理解为 “ 链表的数组 ” ,如图: 从上图我们可以发现哈希表是由 数组 +链表 组成的,一个长度为 16的数组中,每个元 素存储的是一个链表的头结点。 那么这些元素是按照什么样的规则存储到数组中呢。 一般情 况是通过 hash(key)%len获得,也就是元素的 key 的哈希值对数组长度取模得到。比如上 述哈希表中, 12%16=12,28%16=12,108%16=12,140%16=12。 所以 12、 28、 108以及 140都存储在数组下标为 12的位置。 HashMap 其实也是一个线性的数组实现的 , 所以可以理解为其存储数据的容器就是一 个线性数组。 这可能让我们很不解, 一个线性的数组怎么实现按键值对来存取数据呢?这里 HashMap 有做一些处理。 首先 HashMap 里面实现一个静态内部类 Entry ,其重要的属性有 key , value, next,从 属性 key,value 我们就能很明显的看出来 Entry 就是 HashMap 键值对实现的一个基础 bean , 我们上面说到 HashMap 的基础就是一个线性数组,这个数组就是 Entry[], Map 里面的内 容都保存在 Entry[]里面。 /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table ; 2. HashMap的存取实现 既然是线性数组,为什么能随机存取?这里 HashMap 用了一个小 算法 ,大致是这样实现: // 存储时 : int hash =key.hashCode(); // 这个 hashCode 方法这里不详述 , 只要理解每个 key 的 hash 是一 个固定的 int 值 int index = hash % Entry[].length; Entry[index] = value; // 取值时 : int hash =key.hashCode(); int index = hash % Entry[].length; return Entry[index]; 1) put 疑问:如果两个 key 通过 hash%Entry[].length得到的 index 相同,会不会有覆盖的危险? 这里 HashMap 里面用到链式数据结构的一个概念。上面我们提到过 Entry 类里面有一 个 next 属性,作用是指向下一个 Entry 。打个比方,第一个键值对 A 进来,通过计算其 key 的 hash 得到的 index=0, 记做 :Entry[0] = A。 一会后又进来一个键值对 B , 通过计算其 index 也等于 0,现在怎么办? HashMap 会这样做 :B.next = A,Entry[0] = B,如果又进来 C,index 也等于 0, 那么 C.next = B,Entry[0] = C;这样我们发现 index=0的地方其实存取了 A,B,C 三 个键值对 , 他们通过 next 这个属性链接在一起。所以疑问不用担心。 也就是说数组中存储的 是最后插入的元素。 到这里为止, HashMap 的大致实现,我们应该已经清楚了。 public V put(K key, V value) { if (key == null ) return //null总是放在数组的第一个链表中 int hash = hash (key.hashCode()); int i = indexFor (hash, table . length ); //遍历链表 for (Entry Object k; //如果 key 在链表中已存在,则替换为新 value if (e.hash == hash && ((k = e.key ) == key || key.equals(k))) { V oldValue = e.value ; e. value = value; e.recordAccess(this ); return oldValue; } } modCount ++; addEntry(hash, key, value, i); returnnull ; } void addEntry(int hash, K key, V value, int bucketIndex) { Entry table [bucketIndex] = new Entry if (size ++ >= threshold ) resize(2 * table . length ); } 当然 HashMap 里面也包含一些优化方面的实现,这里也说一下。比如:Entry[]的长度 一定后,随着 map 里面数据的越来越长,这样同一个 index 的链就会很长,会不会影响性 能? HashMap 里面设置一个因子,随着 map 的 size 越来越大, Entry[]会以一定的规则加 长长度。 2) get public V get(Object key) { if (key == null ) return getForNullKey(); int hash = hash (key.hashCode()); //先定位到数组元素,再遍历该元素处的链表 for (Entry e != null ; e = e.next ) { Object k; if (e.hash == hash && ((k = e.key ) == key || key.equals(k))) return e. value ; } returnnull ; } 3) null key的存取 null key总是存放在 Entry[]数组的第一个元素。 private V putForNullKey(V value) { for (Entry V oldValue = e.value ; e. value = value; e.recordAccess(this ); return oldValue; } } modCount ++; addEntry(0, null , value, 0); returnnull ; } private V getForNullKey() { for (Entry return e. value ; } returnnull ; } 4)确定数组 index :hashcode % table.length取模 HashMap 存取时,都需要计算当前 key 应该对应 Entry[]数组哪个元素,即计算数组下标; 算法如下: /** * Returns index for hash code h. */ staticint indexFor(int h, int length) { return h & (length-1); } 按位取并,作用上相当于取模 mod 或者取余 %。 这意味着数组下标相同,并不表示 hashCode 相同。 5) table 初始大小 public HashMap(int initialCapacity, float loadFactor) { ..... // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity <> capacity<=> this . loadFactor = loadFactor; threshold = (int )(capacity * loadFactor); table = new Entry[capacity]; init(); } 注意 table 初始大小并不是构造函数中的 initialCapacity !! 而是 >= initialCapacity的 2的 n 次幂!!!! ———— 为什么这么设计呢? —— 3. 解决 hash 冲突的办法 1. 开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列) 2. 再哈希法 3. 链地址法 4. 建立一个公共溢出区 Java 中 hashmap 的解决办法就是采用的链地址法。 4. 再散列 rehash 过程 当哈希表的容量超过默认容量时,必须调整 table 的大小。当容量已经达到最大可能值时, 那么该方法就将容量调整到 Integer.MAX_VALUE返回, 这时,需要创建一张新表,将原表 的映射到新表中。 /** * Rehashes the contents of this map into a new array with a * larger capacity. This method is called automatically when the * number of keys in this map reaches its threshold. * * If current capacity is MAXIMUM_CAPACITY, this method does not * resize the map, but sets threshold to Integer.MAX_VALUE. * This has the effect of preventing future calls. * * @paramnewCapacity the new capacity, MUST be a power of two; * must be greater than current capacity unless current * capacity is MAXIMUM_CAPACITY (in which case value * is irrelevant). */ void resize(int newCapacity) { Entry[] oldTable = table ; int oldCapacity = oldTable.length ; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return ; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable); table = newTable; threshold = (int )(newCapacity * loadFactor ); } /** * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable) { Entry[] src = table ; int newCapacity = newTable.length ; for (int j = 0; j Entry if (e != null ) { src[j] = null ; do { Entry //重新计算 index int i = indexFor (e.hash , newCapacity); e. next = newTable[i]; newTable[i] = e; e = next; } while (e != null ); } } } 哈希表的 C++实现 标签:c++insertdelete测试 search 存储 2012-08-31 16:2110598人阅读 评论 (0) 收藏举报 分类: C/C++(101) 哈希表的几个概念: 映像:由哈希函数得到的哈希表是一个映像。 冲突:如果两个关键字的哈希函数值相等,这种现象称为冲突。 处理冲突的几个方法: 1、开放地址法:用开放地址处理冲突就是当冲突发生时,形成一个地址序列,沿着这个序 列逐个深测,直到找到一个 “ 空 ” 的开放地址,将发生冲突的关键字值存放到该地址中去。 例如:hash(i)=(hash(key)+d(i)) MOD m (i=1,2,3,......,k(k d(i)=d1,d2,d3,...,dn-1 根据增量序列的取法不同,可以得到不同的开放地址处理冲突探测方法。 有线性探测法、二次方探测法、伪随机探测法。 2、链地址法:把所有关键字为同义词的记录存储在一个线性链表中,这个链表成为同义词 链表,即把具有相同哈希地址的关键字值存放在同义链表中。 3、再哈希表:费时间的一种方法 下面是代码: 文件 Cpp 代码 1. #include 2. usingnamespace std; 3. 4. typedef int KeyType; //设关键字域为整形 , 需要修改类型时,只需修改这里就可以 5. const int NULLKEY=0; //NULLKEY表示该位置无值 6. int c=0; //用来统计冲突次数 7. 8. struct Elemtype //数据元素类型 9. { 10. KeyType key; 11. int ord; 12. }; 13. 14. int hashsize[]={11,19,29,37,47}; //hash表容量递增表 15. int Hash_length=0;//hash表表长 16. 17. class HashTable Hash join 算法原理 自从 oracke 7.3以来, oracle 提供了一种新的 join 技术, 就是 hash join 。 Hash Join 只能用于相等连接,且只能在 CBO 优化器模式下。相对于 nested loop join , hash join 更适合处理大型结果集。 Hash join 不需要在驱动表上存在索引。 一. Hash Join 概述 Hash join 算法的一个基本思想就是根据小的 row sources(称作 build input , 我 们记较小的表为 S , 较大的表为 B) 建立一个可以存在于 hash area 内存中的 hash table ,然后用大的 row sources(称作 probe input) 来探测前面所建的 hash table 。 如果 hash area 内存不够大, hash table 就无法完全存放在 hash area 内存中。针对 这种情况, Oracle 在连接键利用一个 hash 函数将 build input 和 probe input 分割 成多个不相连的分区(分别记作 S i 和 B i ) ,这个阶段叫做分区阶段;然后各自相 应的分区,即 S i 和 B i 再做 Hash join ,这个阶段叫做 join 阶段。 如果在分区后, 针对某个分区所建的 hash table 还是太大的话, oracle 就采用 nested-loops hash join 。 所谓的 nested-loops hash join 就是对部分 S i 建立 hash table , 然后读取所有的 B i 与所建的 hash table 做连接, 然后再对剩余的 S i 建立 hash table , 再将所有的 B i 与所建的 hash table 做连接,直至所有的 S i 都连接完了。 Hash Join 算法有一个限制,就是它是在假设两张表在连接键上是均匀的, 也 就是说每个分区拥有差不多的数据。 但是实际当中数据都是不均匀的, 为了很好 地解决这个问题, oracle 引进了几种技术,位图向量过滤、角色互换、柱状图, 这些术语的具体意义会在后面详细介绍。 二. Hash Join 原理 我们用一个例子来解释 Hash Join 算法的原理,以及上述所提到的术语。 考虑以下两个数据集。 S={1,1,1,3,3,4,4,4,4,5,8,8,8,8,10} B={0,0,1,1,1,1,2,2,2,2,2,2,3,8,9,9,9,10,10,11} Hash Join 的第一步就是判定小表 (即 build input ) 是否能完全存放在 hash area 内存中。 如果能完全存放在内存中, 则在内存中建立 hash table , 这是最简单 的 hash join 。 如果不能全部存放在内存中,则 build input 必须分区。分区的个数叫做 fan-out 。 Fan-out 是由 hash_area_size和 cluster size 来决定的。其中 cluster size 等 于 db_block_size*hash_multiblock_io_count, hash_multiblock_io_count在 oracle9i 中 是 隐 含 参 数 。 这 里 需 要 注 意 的 是 fan-out 并 不 是 build input 的 大 小 /hash_ara_size, 也就是说 oracle 决定的分区大小有可能还是不能完全存放在 hash area 内存中。大的 fan-out 导致许多小的分区,影响性能,而小的 fan-out 导致少 数的大的分区,以至于每个分区不能全部存放在内存中,这也影响 hash join 的 性能。 Oracle 采用内部一个 hash 函数作用于连接键上,将 S 和 B 分割成多个分区, 在这里我们假设这个 hash 函数为求余函数, 即 Mod(join_column_value,10)。 这样 产生十个分区,如下表。 分 区 B0B1B2B3B4B5B6B7B8B9值 0,0,10,101,1,1,1,112,2,2,2,2,23NULL NULL NULL NULL 89,9,9 S010√ S11,1,1√ S2Null S33,3√ S44,4,4,4 S55 S6NULL S7NULL S88,8,8,8√ S9NULL 经过这样的分区之后,只需要相应的分区之间做 join 即可(也就是所谓的 partition pairs ) ,如果有一个分区为 NULL 的话,则相应的分区 join 即可忽略。 在将 S 表读入内存分区时, oracle 即记录连接键的唯一值,构建成所谓的位 图向量,它需要占 hash area 内存的 5%左右。在这里即为 {1,3,4,5,8,10}。 当对 B 表进行分区时, 将每一个连接键上的值与位图向量相比较, 如果不在 其中,则将其记录丢弃。在我们这个例子中, B 表中以下数据将被丢弃 {0,0,2,2,2,2,2,2,9,9,9,9,9}。这个过程就是位图向量过滤。 当 S1,B1做完连接后,接着对 Si,Bi 进行连接,这里 oracle 将比较两个分区, 选取小的那个做 build input ,就是动态角色互换,这个动态角色互换发生在除第 一对分区以外的分区上面。 三. Hash Join 算法 第 1步:判定小表是否能够全部存放在 hash area 内存中,如果可以, 则做内 存 hash join 。如果不行,转第二步。 第 2步:决定 fan-out 数。 (Numberof Partitions) *C<=f avm=""> 其中 C 为 Cluster size , 其值为 DB_BLOCK_SIZE*HASH_MULTIBLOCK_IO_COUNT; F avm 为 hash area 内存可以使用的百分比, 一般为 0.8左右; M 为 Hash_area_size的大小。 第 3步:读取部分小表 S ,采用内部 hash 函数 (这里称为 hash_fun_1),将连 接键值映射至某个分区, 同时采用 hash_fun_2函数对连接键值产生另外 一个 hash 值, 这个 hash 值用于创建 hash table 用, 并且与连接键值存放 在一起。 第 4步:对 build input 建立位图向量。 第 5步:如果内存中没有空间了,则将分区写至磁盘上。 第 6步:读取小表 S 的剩余部分,重复第三步,直至小表 S 全部读完。 第 7步:将分区按大小排序,选取几个分区建立 hash table(这里选取分区的 原则是使选取的数量最多 ) 。 第 8步:根据前面用 hash_fun_2函数计算好的 hash 值,建立 hash table 。 第 9步:读取表 B ,采用位图向量进行位图向量过滤。 第 10步:对通过过滤的数据采用 hash_fun_1函数将数据映射到相应的分区 中去,并计算 hash_fun_2的 hash 值。 第 11步:如果所落的分区在内存中,则将前面通过 hash_fun_2函数计算所 得的 hash 值与内存中已存在的 hash table 做连接, 将结果写致磁盘上。 如果所落的分区不在内存中, 则将相应的值与表 S 相应的分区放在一起。 第 12步:继续读取表 B ,重复第 9步,直至表 B 读取完毕。 第 13步:读取相应的 (Si,Bi)做 hash 连接。在这里会发生动态角色互换。 第 14步:如果分区过后,最小的分区也比内存大,则发生 nested-loop hash join 。 四. Hash Join 的成本 1. In-Memory Hash Join Cost(HJ)=Read(S)+build hash table in memory(CPU)+Read(B)+ Perform In memory Join(CPU) 忽略 cpu 的时间,则 Cost(HJ)=Read(S)+Read(B) 2. On-Disk Hash Join 根据上述的步骤描述,我们可以看出 Cost(HJ)=Cost(HJ1)+Cost(HJ2) 其中 Cost(HJ1)的成本就是扫描 S,B 表,并将无法放在内存上的部分写回 磁盘,对应前面第 2步至第 12步。 Cost(HJ2)即为做 nested-loop hash join 的成本,对应前面的第 13步至第 14步。 其中 Cost(HJ1)近似等于 Read(S)+Read(B)+Write((S-M)+(B-B*M/S))。 因为在做 nested-loop hash join 时,对每一 chunk 的 build input ,都需要读 取整个 probe input ,因此 Cost(HJ2)近似等于 Read((S-M)+n*(B-B*M/S)) 其中 n 是 nested-loop hash join 需要循环的次数。 n=(S/F)/M 一般情况下,如果 n 在于 10的话, hash join 的性能将大大下降。从 n 的 计算公式可以看出, n 与 Fan-out 成反比例,提高 fan-out ,可以降低 n 。 当 hash_area_size是固定时,可以降低 cluster size 来提高 fan-out 。 从这里我们可以看出,提高 hash_multiblock_io_count参数的值并不一定 提高 hash join 的性能。 五. 其它 1.确认小表是驱动表 2.确认涉及到的表和连接键分析过了。 3.如果在连接键上数据不均匀的话,建议做柱状图。 4.如果可以,调大 hash_area_size的大小或 pga_aggregate_target的值。 5. Hash Join 适合于小表与大表连接、返回大型结果集的连接。 实验报告 实验一 <哈希函数的实现> 实验一 HASH 函数的实现 1 实验要求 利用 c 语言实现 MD5、 SHA-1, 能够对任意长的消息值进行压缩 至定长。 在实现的同时需要保持效率, 这是好的压缩函数所必须具备 的,所以我们在程序最后迭代压缩一万次,并记录使用时间 . 2 算法流程介绍 1).MD5 步骤 1:填充报文,填充报文的目的是使报文长度与 448模 512同余(即长度 =448 mod 512) 。若报文本身已经满足上述长度要求, 仍然需要进行填充,因此填充位数在 1-512之间。填充方法是在报文 后附加一个 1和若干个 0,然后附上表示填充前报文长度的 64位数 据(最低有效位在前) 。若填充前报文长度大于 2^44,则只取其低位 64位。 步骤 2:初始化缓冲区。 Md5函数的中间结果和最终结果保存在 128位的缓冲区(A,B,C,D )中,其中 A,B,C,D 均为 32位,其初始值 分别为下列整数(十六进制) : A :67452301 B :EFCDAB89 C :98BADCFE D :10325476 这些初始值存储方式为小端存储, 即最低有效位存储在低字节位 置。 步骤 3:执行算法主循环。每次循环处理一个 512位的分组,故 循环次数为填充后报文的分组数。 算法核心是压缩函数,它由四轮算法组成,四轮运算结构相同。 每轮的输入是当前要处理的 512位的分组和 128位缓冲区的 ABCD 的内容。每轮所使用的逻辑函数分别为 F,G ,H 和 I 。第四轮的输出与 第一轮的输入相加得到压缩函数的输出。 步骤 4:输出。所有的 512分组处理完之后,最后一个分组的输 出即是 128位的报文摘要。 关于每轮对 512位分组的处理过程如下,需要对缓冲区 ABCD 进行 16步的迭代,因此压缩函数共有 64步,每步的迭代形式为 A,B,C,D ← D,B+((A+g(B,C,D)+X[k]+T[i])<> 其中 A,B,C,D 为缓冲区的四个字, g 为基本逻辑函数 F,G ,H,I 之 一, 四个轮函数 F,G ,H 和 I ,其输入均为三个 32位的字,输出为 32位的字,执行位逻辑运算,其定义为: (, , ) () () (, , ) () () (, , ) (, , ) () F b c d b c b d G b c d b d c d H b c d b c d I b c d c b d =∧∨?∧=∧∨∧?=⊕⊕=⊕∨? 每轮使用 T[1,? ,64]中的 16个元素, T 通过正弦函数构造, 具体 值不再赘述,另外对于待处理的 512分组, 16个字的消息块,在每 轮中的使用顺序有规定,具体为,第一轮为初始顺序呢,第二轮至第 四轮由如下置换确定: 234() (15) mod16 () (53) mod16() 7mod16 i i i i i i ρρρ=+=+= 2).SHA-1 因为同为 MD 结构的哈希函数,这里关于 SHA-1的算法介绍相 对简化一些,重点提出和 md5不同的地方。 步骤 1:仍是报文填充,块长类同 MD5,需要注意的是 SHA-1使用的是大端存储, 和 MD5正好相反, 具体处理见后面的程序实现。 步骤 2:初始化缓冲区,这里需要注意, SHA-1多了一个 32位 寄存器,也就是最终结果为 160位,寄存器初始值前四个与 MD5一 样,新增一个 E=C3D2E1F0。 步骤 3:执行算法主循环,类同 MD5, 每次处理 512位分组, 80步,分四轮,每轮 20步,单步的细节如下 , , , , , ((, , ,) (5) ), ,(30), , t t t A B C D E E f B C D A W K A B C D ←++<>< 与=""> 152483015 () 11679t t t t t t t W M t W W W W W t ----=≤≤=⊕⊕⊕<≤≤若> 其他的参量不再赘述,详见下面的算法实现。 3实现细节与心得 我编写了一个 digest 的工程,集成了 MD5和 SHA-1,下面介绍我 的实验细节, 我以 MD5的实现介绍为主, 然后补充介绍 SHA-1特别的 部分。 1)头文件“ cryptoConfig.h ” : 该文件中主要是包括对 unsigned int和 unsigned char的重新定义, 另外以宏定义的方式定义了对于一个字的循环左移、 循环右移、 左移 和右移。 2)头文件“ digest.h ” : 定义本程序所要使用的数据结构和声明主要函数, 具体的定义了 一个名为 MD5_CTX的结构体变量,结构体成员包括了四个寄存器的 字, 64位的消息长度, 512位的单轮消息块,和新变量“ curlen ”,用 来标记还没压缩的消息长度,后面实现时会发现,有这样一个变量, 在进行动态内存分配时显得非常方便, 我们的目的就是不多使用一丁 点的内存。 主要的功能函数包括 int MD5_Init(MD5_CTX *ctx):对 512位的带压缩消息块进行初始 化; int MD5_Update(MD5_CTX *ctx, const unsigned char *data, size_t len):对进来的数据进行填充,当 buffer 空间满了之后实现压缩,循环 进行压缩,只留最后一块; int MD5_Final(unsigned char *md, MD5_CTX *ctx):对最后一块或 者两块进行填充,并将最后的寄存器字级联之后赋给指针 md 。 SHA-1的结构体变量 SHA-1_CTX和三个功能函数的声明也在这 个头文件里,结构和作用类同。 3)” md5.cpp ” : 主要对三个功能函数进行功能实现, 首先先宏定义四个非线性函 数 F,G,H,I ,并宏定义四个轮函数 FF,GG,HH,II, 以 FF 为例,有 #define FF(a, b, c, d, Mj, s, ti) a = b + ROTL(a + F(b,c,d) + Mj + ti, s) 定义并实现函数 MD5_compress(MD5_CTX *ctx),即单轮压缩,来 对结构体变量 ctx 中的 512位的 buf 值进行压缩,共 64步,第一步的输 入加上最后一步的输出存储于寄存器中。 实现函数 MD5_Init( ),完成功能为重置结构体变量 ctx 的成员, 寄存器赋初值,待压缩长度清 0,内存空间清 0。 实现函数 MD5_Update( ),完成功能为输入消息块的分组,即 padding 过程,如何 512位的分块,如何合理的使用内存,这是 MD5中 的难点也是关键点, 我的设计如下, 当输入消息长度大于 buffer 剩余 空间时,做如下操作: A . 先将剩余的 buffer_space塞满做一次 transform(压缩 ) ; B . 循环做 64个 bytes的 transform 直至 input_index(输入的 消息长度 ) 小于剩余的 buffer_space; C . Padding! A,B 的操作由 Update( )实现,将输入长度 len 由位数转换为 byte 数 之后赋给 length[1]、 length[2],然后根据目前已存的数据长 curlen ,向 buf 里填充数据, 保证写入数据不会超长和溢出, 一旦 curlen 满 64byte 了就进行一次压缩, 实现了之前的循环填充和压缩。 (注:bits 转 byte , 右移三位即可) C 的操作由接下来的 MD5_Final( )实现,此时只剩最后一组 block ,长 度不足 64个 bytes ,加上 panding ,压缩,并将最后的寄存器值并联之 后赋给指针 md(md5对数的存储与内存的栈的存储方式一致,所以这 里并不需要多做处理, SHA-1中不同 ) ,我的尾巴 pad 的定义为 const uint8 PAD[64] = { 0x80 }; 4)” sha1.cpp ” : 定义两个函数 unit32_to_unit8,unit_to_uint32,完成 byte 与 word 互 换的同时完成大端存储,另外有消息块的扩展,其他的类同于 MD5, 就不再叙述了。 5)“ digest_text.cpp” 提供一组测试数据, 并将 MD5和 SHA-1迭代执行一万次, 并统计 时间,详见下面的结果截屏。 4 实验结果截屏 有趣的是 SHA-1的消耗时间差不多是 MD5的四倍 一致性 hash 算法(consistent hashing ) 张亮 consistent hashing 算法早在 1997 年就在论文 中被提出,目前在 cache 系统中应用越来越广泛; 1 基本场景 比如你有 N 个 cache 服务器(后面简称 cache ) ,那么如何将一个对象 object 映射 到 N 个 cache 上呢,你很可能会采用类似下面的通用方法计算 object 的 hash 值,然后 均匀的映射到到 N 个 cache ; hash(object)%N 一切都运行正常,再考虑如下的两种情况; 1 一个 cache 服务器 m down 掉了 (在实际应用中必须要考虑这种情况) , 这样所有映射到 cache m 的对象都会失效, 怎么办, 需要把 cache m 从 cache 中移除, 这时候 cache 是 N-1 台,映射公式变成了 hash(object)%(N-1) ; 2 由 于 访 问 加 重 , 需 要 添 加 cache , 这 时 候 cache 是 N+1 台 , 映 射 公 式 变 成 了 hash(object)%(N+1) ; 1 和 2 意味着什么?这意味着突然之间几乎所有的 cache 都失效了。对于服务器而 言,这是一场灾难,洪水般的访问都会直接冲向后台服务器; 再来考虑第三个问题,由于硬件能力越来越强,你可能想让后面添加的节点多做点活, 显然上面的 hash 算法也做不到。 有什么方法可以改变这个状况呢,这就是 consistent hashing... 2 hash 算法和单调性 Hash 算法的一个衡量指标是单调性(Monotonicity ) ,定义如下: 单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中, 又有新的缓冲加入到 系统中。 哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去, 而不会被映 射到旧的缓冲集合中的其他缓冲区。 容易看到,上面的简单 hash 算法 hash(object)%N 难以满足单调性要求。 3 consistent hashing 算法的原理 consistent hashing 是一种 hash 算法,简单的说,在移除 / 添加一个 cache 时,它能 够尽可能小的改变已存在 key 映射关系,尽可能的满足单调性的要求。 下面就来按照 5 个步骤简单讲讲 consistent hashing 算法的基本原理。 3.1 环形 hash 空间 考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值,也即是 0~2^32-1 次方的数值空间;我们可以将这个空间想象成一个首(0 )尾(2^32-1 )相接的圆环, 如下面图 1 所示的那样。 图 1 环形 hash 空间 3.2 把对象映射到 hash 空间 接下来考虑 4 个对象 object1~object4 , 通过 hash 函数计算出的 hash 值 key 在环上 的分布如图 2 所示。 hash(object1) = key1; … … hash(object4) = key4; 图 2 4 个对象的 key 值分布 3.3 把 cache 映射到 hash 空间 Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间 中,并且使用相同的 hash 算法。 假设当前有 A,B 和 C 共 3 台 cache , 那么其映射结果将如图 3 所示, 他们在 hash 空间中,以对应的 hash 值排列。 hash(cache A) = key A; … … hash(cache C) = key C; 图 3 cache 和对象的 key 值分布 说到这里, 顺便提一下 cache 的 hash 计算, 一般的方法可以使用 cache 机器的 IP 地 址或者机器名作为 hash 输入。 3.4 把对象映射到 cache 现在 cache 和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了, 接下来要 考虑的就是如何将对象映射到 cache 上面了。 在这个环形空间中, 如果沿着顺时针方向从对象的 key 值出发, 直到遇见一个 cache , 那么就将该对象存储在这个 cache 上,因为对象和 cache 的 hash 值是固定的,因此这个 cache 必然是唯一和确定的。这样不就找到了对象和 cache 的映射方法了吗?! 依然继续上面的例子(参见图 3 ) ,那么根据上面的方法,对象 object1 将被存储到 cache A 上; object2 和 object3 对应到 cache C ; object4 对应到 cache B ; 3.5 考察 cache 的变动 前面讲过,通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性,当 cache 有所变动时, cache 会失效, 进而对后台服务器造成巨大的冲击, 现在就来分析分析 consistent hashing 算法。 3.5.1移除 cache 考虑假设 cache B 挂掉了,根据上面讲到的映射方法,这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache (cache C ) 之间的对象, 也即是本来映射到 cache B 上的那些对象。 因此这里仅需要变动对象 object4 ,将其重新映射到 cache C 上即可;参见图 4 。 图 4 Cache B 被移除后的 cache 映射 3.5.2添加 cache 再考虑添加一台新的 cache D 的情况,假设在这个环形 hash 空间中, cache D 被映 射在对象 object2 和 object3 之间。这时受影响的将仅是那些沿 cache D 逆时针遍历直到 下一个 cache (cache B )之间的对象(它们是也本来映射到 cache C 上对象的一部分) , 将这些对象重新映射到 cache D 上即可。 因此这里仅需要变动对象 object2 ,将其重新映射到 cache D 上;参见图 5 。 图 5 添加 cache D 后的映射关系 4 虚拟节点 考量 Hash 算法的另一个指标是平衡性 (Balance) ,定义如下: 平衡性 平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去, 这样可以使得所有的缓冲空 间都得到利用。 hash 算法并不是保证绝对的平衡, 如果 cache 较少的话, 对象并不能被均匀的映射到 cache 上,比如在上面的例子中,仅部署 cache A 和 cache C 的情况下,在 4 个对象中, cache A 仅存储了 object1 ,而 cache C 则存储了 object2 、 object3 和 object4 ;分布是很不 均衡的。 为了解决这种情况, consistent hashing 引入了“虚拟节点”的概念, 它可以如下定义:“虚拟节点”(virtual node )是实际节点在 hash 空间的复制品(replica ) ,一实际 个节点对应了若干个“虚拟节点”,这个对应个数也成为“复制个数”,“虚拟节点”在 hash 空间中以 hash 值排列。 仍以仅部署 cache A 和 cache C 的情况为例,在图 4 中我们已经看到, cache 分布 并不均匀。 现在我们引入虚拟节点, 并设置“复制个数”为 2 , 这就意味着一共会存在 4 个 “虚拟节点”, cache A1, cache A2 代表了 cache A ; cache C1, cache C2 代表了 cache C ;假设一种比较理想的情况,参见图 6 。 图 6 引入“虚拟节点”后的映射关系 此时,对象到“虚拟节点”的映射关系为: objec1->cache A2 ; objec2->cache A1 ; objec3->cache C1 ; objec4->cache C2 ; 因此对象 object1 和 object2 都被映射到了 cache A 上, 而 object3 和 object4 映射到 了 cache C 上;平衡性有了很大提高。 引入“虚拟节点”后,映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节 点 } 。查询物体所在 cache 时的映射关系如图 7 所示。 图 7 查询对象所在 cache “虚拟节点”的 hash 计算可以采用对应节点的 IP 地址加数字后缀的方式。 例如假设 cache A 的 IP 地址为 202.168.14.241 。 引入“虚拟节点”前,计算 cache A 的 hash 值: Hash(“202.168.14.241”); 引入“虚拟节点”后,计算“虚拟节”点 cache A1 和 cache A2 的 hash 值: Hash(“202.168.14.241#1”); // cache A1 Hash(“202.168.14.241#2”); // cache A2 5 小结 Consistent hashing 的基本原理就是这些,具体的分布性等理论分析应该是很复杂的, 不过一般也用不到。 上面有一个 java 版本的例子, 可以参考。 转载了一个 PHP 版的 实现代码。 http://www.codeproject.com/KB/recipes/lib-conhash.aspx C语言版本 一些参考资料地址:范文二：hash原理
范文三：hash_join算法原理
范文四：实验报告--hash
范文五：一致性 hash 算法
