数据结构——散列表

散列表，又称哈希表。
散列表同样是一个比较神奇的数据结构，其基本思想在于将一个无穷集合映射到一个固定集合之中，从而实现快速查找。
这里实现一个简单的散列表，假定插入元素均不相同，且指定元素类型为 int。

结构

// 散列表结构
class Hash {
    int capacity; // hash数组固定长度
    Node* data; // 这里采用链地址法解决冲突问题
}

函数实现

初始化

// 默认构造函数
Hash()
{
    this->capacity = 100019; // 该数为质数，选择质数作为数组长度，尽可能保证散列均匀
    this->data = new Node[this->capacity];
}

增加

// 将关键字转换为hash码，即固定数组下标
int hash(int value)
{
    value = (value + this->capacity) % this->capacity;
    return value;
}

// 向散列表中插入一个元素
void insert_elem(int value)
{
    int index = hash(value);
    Node* pre = this->data + index,*p = pre->next;
    while(p)
    {
        if(p->value == value)
            break;
        pre = p;
        p = p->next;
    }
    if(!p) // p为空，表明没有遇到相同的值
        pre->next = new Node(value);
}

删除

// 从散列表中删除一个元素
void delete_elem(int value)
{
    int index = hash(value);
    Node* pre = this->data + index,*p = pre->next;
    while(p)
    {
        if(p->value == value)
            break;
        pre = p;
        p = p->next;
    }
    if(p) // p为空，表明遇到相同的值
    {
        pre->next = p->next;
        delete p;
    }
}

// 清理每一条链
void clear_chain(Node* head)
{
    Node* p = head->next;
    while(p)
    {
        Node* tmp = p->next;
        delete p;
        p = tmp;
    }
}

// 清空散列表
void clear()
{
    for(int i = 0;i < this->capacity;i++)
    {
        clear_chain(this->data + i);
        this->data[i].next = NULL;
    }
}

修改

此处不涉及修改操作，因为插入元素即为关键字。

查找

// 查询关键字是否存在
bool contains(int value)
{
    int index = hash(value);
    Node* p = this->data + index;
    while(p)
    {
        if(p->value == value)
            return true;
        p =p->next;
    }
    return false;
}

销毁

// 析构函数
~Hash()
{
    for(int i = 0;i < this->capacity;i++)
        clear_chain(this->data + i);
    delete[] this->data;
}