哈希表

哈希表主要考虑两个问题：1）如何设计哈希函数2）如何解决冲突

hash函数计算出元素在hash表中的储存位置：locate(i)=hash(keyi)hash表用于存储元素

第1节 hash函数构造方法

1）直接定址法：Hash（key）=a*Key+b优点:以关键码key的某个线性函数值为散列地址,不会产生冲突。缺点: 要占用连续地址空间,空间效率低。

2）除留余数法：Hash(Key)=Key % p (设表长未m，取p为小于等于m的质数)优点：节约空间缺点：会产生冲突

第2节 处理冲突的方法

1）开放地址法：Hi=(Hash(key)+di) % m当d为1，2，3……这个线性序列时，叫做线性探测法当d为1，2，3……的平方时，叫做二次序列当d也可以为伪随机数（我猜测这样的话可能需要用一张表事先记录伪随机序列，获取随机数时就从这张表来获取）

2）链地址法：将相同散列地址的元素组成一个链表，那么用数组是应该存储链表的元素还是地址呢？换言之，数组元素的存储结构应该是怎样的？

其它：再散列法（双散列函数）建立一个公共溢出区

一个结论：链地址法优于开发地址法。除留余数法作为散列函数优于其它类型函数。所以在本章节中，只学习和使用链式哈希表。

第3节 链式哈希表

哈希表的存储结构

// 链表结点
typedef struct ListNode
{
    int data;
    struct ListNode *next;
}ListNode;

typedef struct ListNode *List;
typedef struct HashTable
{
    int tableSize;
    List *table; // 优于List table[MAXSIZE];
}HashTable;

哈希表的算法实现

// 哈希表初始化,返回一个指向Hash表的指针
HashTable initHashTable(int size)
{
    HashTable *H=malloc(sizeof(struct HashTable));
    H->tableSize=size;
    H->table=malloc(sizeof(List)*H->tableSize);

    // 为每个链表增加一个虚拟头结点
    for(int i=0;i<H->tableSize;i++)
    {
        H->table[i]=malloc(sizeof(struct ListNode));
        if(H->table[i]==NULL)
        {
            return NULL:
        }
        H->table[i]->next=NULL:
    }
    return H;
}

// 哈希表查找
ListNode* find(int key,HashTable* H)
{
    ListNode* p;
    List L;

    L=H->table[hash(key)];
    p=L->next;
    while(p!=null&&p->data！=key)
    {
        p=p->next;
    }
    return p;
}

// 哈希表插入
void insert(int key,HashTbale *H)
{
    ListNode* pos;
    pos=find(key,H);
    if(pos==NULL)
    {
        ListNode *p=new ListNode;
        L=H->table[hash(key)];
        p->next=L->next;
        p->data=key;
        L-next=p;
    }
}

注：如果哈希表的操作中不包含删除，那么就无需为链表添加头结点。但如果包含的话，最好还是使用头结点吧！