注意：
    这里说的原子并不是原子操作！！！！
    此处的原子源于LISP。
    原子是一个指针，指向唯一的一个字符序列。
    通过比较两个指针的值，即可判断两者指向的字符串是否相等，原因在于，任一字符序列只会出现一次！！！！


已完成基础的插入，后续还剩下 查找，比较等。

如果代码有任何BUG、或你有任何疑问、或建议，请提出，不胜感激。

冲突一定是会发生的，为了解决冲突，因此结构上使用了链表。

22：43 06/14
            修改了散列函数，冲突明显减少。
00：39 06/15
            修改了数列，虽然并未减少冲突，但是让散列值分布较之前更加均匀。
            经测试读取一个9800个无重复单词的文本文档，发生冲突的几率是22%，链表的节点数均在3左右，最多节点数达到5。
16：24 06/15
            查找、判断函数已完成。
19：05 06/15
            已完成将长整数插入原子表。
20：53 06/16
            已完成将浮点数插入原子表。

/*测试*/

#include <stdio.h>
#include <string.h>
#include "Atom.h"

int
main( void )
{
    char src[ 100 ];
    char *des;

    while( NULL != fgets( src, 100, stdin ) )
    {
        src[ strlen( src ) - 1 ] = '\0';
        des = NewAtom( src );
        printf( "%s\n", des );
    }

    return 0;
}

/*接口*/
#ifndef _ATOM_H
#define _ATOM_H

char *
NewAtom( char *src );
/*将一个字符串添加到原子表中，如果该字符串已经存在，则返回位于原子表中的该字符串，否则添加到原子表并且返回位于原子表中的该字符串。
任何试图修改原子的行为是无法检测的错误。*/

char *
IntAtom( long value );
/*将一个长整数转换为字符串，添加到原子表中，如果该字符串已经存在，则返回位于原子表中的该字符串，否则将该字符串添加到原子表并且返回位于原子表中的该字符串。
任何试图修改原子的行为是无法检测的错误。*/


char *
DoubleAtom( double value, int length );
/*将一个浮点数转换为字符串，添加到原子表中，如果已经存在则返回原子表中的该字符串，否则将该字符串添加到原子表并且返回该字符串。
DoubleAtom（）函数的第一个参数为需要添加到原子表中的浮点数，第二个参数为小数点后数字的长度。
length不可以小于0，如果小于0则返回NULL。
*/

char *
FindAtom( char *src );
/*在原子表中查找一个字符串，如果在表中，返回原子表中的该字符串，否则返回NULL
任何试图修改原子的行为是无法见车的错误*/

int
DetermineAtom( char *src, char *dst );
/*判断两个原子指向的字符串是否相等，向该函数传递非源自原子表中的指针是无法检测的错误
相等返回1，否则返回0*/

void
chongtu1( void );/*测试用函数，可删除*/
#endif

/*实现*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "Atom.h"
#define EvenKey 101
#define OddKey 211
#define H Hash
typedef struct H *H;
#define K Key

struct K {
    unsigned long int Even;
    unsigned long int Odd;
    int Len;
};

struct H{
    H Link;
    int Len;
    char *Src;
};

static H HashTable[ EvenKey ][ OddKey ];

static struct K
HashFun( char *src );

char *
NewAtom( char *src )
{
    struct K key;
    H this;
    H new;

    if( NULL == src )
        return NULL;

    key = HashFun( src );

    for( this = HashTable[ key.Even ][ key.Odd ]; NULL != this; this = this->Link )
        if( key.Len == this->Len )
            if( 0 == strcmp( src, this->Src ) )
                return this->Src;

    new = ( H )malloc( sizeof( struct H ) );
    if( NULL == new )
    exit( EXIT_FAILURE );
    new->Len = key.Len;
    new->Src = strdup( src );
    new->Link = HashTable[ key.Even ][ key.Odd ];
    HashTable[ key.Even ][ key.Odd ] = new;

    return new->Src;
}

int
DetermineAtom( char *src, char *dst )
{
    return src == dst;
}


char *
FindAtom( char *src )
{
    struct K key;
    H this;

    key = HashFun( src );

    for( this = HashTable[ key.Even ][ key.Odd]; NULL != this; this = this->Link )
        if( key.Len == this->Len )
            if( 0 == strcmp( src, this->Src) )
                return this->Src;

    return NULL;
}


#include <limits.h>
void
ItoS( unsigned long value, char *buffer );

char *
IntAtom( long value )
{
    char buffer[ 100 ];
    unsigned long n;

    if( LONG_MIN == value )
    {
        n = LONG_MAX + 1UL;
        buffer[ 0 ] = '-';
        ItoS( n, buffer + 1 );
    }
    else if( 0 > value )
    {
        n = -value;
        buffer[ 0 ] = '-';
        ItoS( n, buffer + 1 );
    }
    else
        ItoS( value, buffer );;

    return NewAtom( buffer );
}


char *
DoubleAtom( double value , int length )
{
    char buffer[ 100 ];
    char *src;
    unsigned long power;
    double integer;
    double devimal;

    src = buffer;
    power = pow( 10, length );    

    if( 0 > value )
    {
        value *= -1;
        *src++ = '-';
    }

    devimal = modf( value, &integer );
    devimal *= power;
    ItoS( ( unsigned long )value, src );

    if( 0 != ( unsigned long )devimal )
    {
        int length = strlen(src);
        src[ length++ ] = '.';
        src[ length ] = '\0';
        ItoS( ( unsigned long )devimal, &src[ length ]);
    }

    return NewAtom( buffer );    
}


void
ItoS( unsigned long value, char *buffer )
{
    static int ix = 0;

    if( 0 != value / 10 )
        ItoS( value / 10, buffer );
    else
        ix = 0;

    buffer[ ix++ ] = value % 10 + '0';
    buffer[ ix ] = '\0';
}



static unsigned long int scatter[] = 

{763886,98427677,92132,8985211,13039125,24243037,3301847,59153526,33682303,59871667,2427280,63468416,32036220,36579419,54565969,88329145,65162120,80548711,97819618,24188516,90161124,29694574,912717

33,83294586,8342758,6132648,38282737,12987094,97193732,4179587,12266336,3036295,2585741,83131394,21439985,8521426,24979665,81878169,4426519,56103885,8278484,82839570,76081111,59512197,2518751,46884

362,1881190,69327849,4350926,3881300,20162120,25741213,65855507,86483029,51586458,73342808,56754322,40931767,40079146,74331877,49054083,32127559,355490,98962454,3614643,36314919,93276160,10015213,2

808739,387580,7826681,62762801,71611367,27236721,5992993,7143959,43431560,6222210,5467604,35719894,15008883,52829025,73163041,72121897,22794936,3976693,39427257,11816449,93372508,84363894,98438213,

69143257,52249272,83662259,71171005,93724481,2223663,49325772,53039410,93291499,2668699,28877224,38669365,6013633,74264121,89221968,23854237,28506493,44054328,13154706,67653109,19177199,3206486,283

07599,31531019,4206922,67706420,85556941,1271355,7529831,18846373,14516070,37538210,53272913,1327634,39271927,4280435,73248024,38623417,60415090,85059333,2041599,1294746,80323900,48358219,425589,45

59456,84163312,16375,79208671,75848350,57761050,5372448,8754836,67779544,22839116,78482152,6115560,26503349,70711533,20895590,60789818,97641356,977253,721025,57114446,16306660,43275651,6949483,7031

6811,26901210,16285927,26767451,3307438,41737694,20803560,11028044,12054262,32029542,35907903,63191356,52829286,68406538,66281290,5478517,185494,4558551,37349290,61047847,63481161,88952733,18194614

,77244724,8039728,2749281,21824485,3984467,91862302,9173219,3821671,41638702,43176491,20199960,44476653,62493364,85413794,84736745,18631309,9418487,47801626,60753091,4425439,42276238,4247976,705395

7,1113555,60525829,52625011,73234853,64327448,45458665,19279463,2562731,12143942,58894828,39004963,262952,18981190,15215655,325683,2973033,65251844,58104562,96943559,4733669,7473324,29673054,558693

62,94432250,39907562,56881884,66066043,5847501,68945840,81133107,5119999,39524518,16173428,58767743,4218541,2500641,4744839,23396012,90303049,98584351,3896895,51434895,28441306,13578262,53589942,78

687629,18106700,16908972,8034409,64662849,4523895
};

static int chongtu[ EvenKey ][ OddKey ];/*测试用数组，可删除*/

void
chongtu1( void )/*测试用函数，可删除*/
{
    int i,j;
    int count;
    
    for( i = 0, count = 0;EvenKey > i;++i )
        for( j = 0; OddKey > j; ++j )
        {
            if( 1 < chongtu[i][j] )
                printf( "冲突发生在 %d %d， 发生了 %d 次\n", i, j, chongtu[i][j] );
            if( 0 == chongtu[i][j] )
                count++;
        }

    printf( "%d个空间未被散列到\n",count );
        
}


static struct K
HashFun( char *src )
{
    struct K key;
    int ix;

    key.Len = strlen( src );
    key.Even = 0;
    key.Odd = 0;

    for( ix = 0; key.Len > ix; ++ix )
    {
        key.Even = ( key.Even << 1 ) + scatter[ ( unsigned )*( src + ix ) ];
        ++ix;
        if( key.Len > ix )
            key.Odd = ( key.Odd << 1 ) + scatter[ ( unsigned )*( src + ix ) ]; 
    }

    key.Even %= EvenKey;
    key.Odd %= OddKey;

    ++chongtu[ key.Even ][ key.Odd ];/*该语句为测试用，可删除*/

    return key;
}

[此贴子已经被作者于2017-6-16 23:46编辑过]

冲突还是发生的挺频繁的。我读取一个85.3kb的文件，冲突就我肉眼就看到3次。

用来生成Key的。

是这样。我用随机函数生成的。

我再一次测试，冲突一定是会发生，但是同一个Key出现的次数并不频繁，所以链表很短，最长的节点为13，但是只出现过一次，其他的也就4左右。（而且字符串比较首先比较长度，只有长度相等才会比较字符串，所以还是很快的。）
但是现在的问题是很多空间没有被散列到，也就是说，很大的空间被浪费了。

PS：我读取了一个85Kb的文件，文件中没有重复的单词。

[此贴子已经被作者于2017-6-14 22:13编辑过]

可以的。将Int行转换为字符串就可以了。但是还是挺麻烦的，慢慢来吧。

要比速度的话，应该没有哪个好玩的字典树快。

这个表的问题在于，空间浪费，我读取的那个文本中有9682个单词，但是竟然有16883个空间没有被散列到，也就是说，只用到了4428个空间。

散列函数我还得继续修改。

简单的修改之后，冲突减少了很多，未被散列到的空间也明显减少。

那倒不用，散列函数修改之后，冲突明显减少，节点数平均在2至3，所以寻找目标字符串很快。

发生冲突的可能是 22%，还是太多了。

[此贴子已经被作者于2017-6-14 23:01编辑过]

随机数列也就256个，对比其他的，显得微不足道。

散列表的核心在散列函数，第一是快，第二是生成的Key要尽可能的少冲突。

随机数列可以让散列值分布更平均（经验表明）

[此贴子已经被作者于2017-6-14 23:10编辑过]

动态散列表，要实现起来并不困难。
难点在于，如果要扩充的话，那么就需要再散列，这要用很多时间。

[此贴子已经被作者于2017-6-14 23:06编辑过]