hash 表 --- 链地址法解决冲突

一般在ACM比赛中，将hash表的大小设置的比较大， 如下hash表仅为了测试方便，
故意将SIZE，M设置的比较小。

顺序存储

hashtable.h

#include
#include

struct Node 
{
    Node(): next(0), key(0), value() {}
    Node(int n, int k, int v)
        : next(n), key(k), value(v) {}

    int next;
    int value;
    int key;
};

class HashTable 
{
public:
    HashTable();
    ~HashTable();
    int hash(int key);
    int search(int key);
    int insert(int key, int value);
    bool modify(int key, int value);
    void show();

private:
    //const int SIZE = 1000000;
    //const int M = 999997;
    static const int SIZE;
    static const int M;
    Node *ht;
    int *head;
    int size;
};

const int HashTable::SIZE = 100;
const int HashTable::M = 3;

HashTable::HashTable()
{
    ht = new Node[SIZE];
    memset(ht, 0, sizeof(Node)*SIZE);
    head = new int[M];
    memset(head, 0, sizeof(int)*M);
    size = 0;
}

HashTable::~HashTable()
{
    if (ht != nullptr)
        delete[] ht;
    if (head != nullptr)
        delete[] head;
}

int HashTable::hash(int key)
{
    return key % M;
}

int HashTable::search(int key) 
{
    for (int i = head[hash(key)]; i > 0; i = ht[i].next)
        if (ht[i].key == key)
            return ht[i].value;

    return -1;
}

int HashTable::insert(int key, int value)
{
    if (search(key) != -1) 
        return -1;

    ht[++size] = Node(head[hash(key)], value, key);
    head[hash(key)] = size;

    return value;
}

bool HashTable::modify(int key, int value)
{
    for (int i = head[hash(key)]; i > 0; i = ht[i].next)
        if (ht[i].key == key)
        {
            ht[i].value = value;
            return true;
        }

    return false;
}

void HashTable::show()
{
    for (int i = 0; i < M; ++i)
    {
        if (head[i] > 0)
        {
            std::cout << i << " : ";
            int index = head[i];
            while (index > 0)
            {
                std::cout << ht[index].value;
                index = ht[index].next;
                if (index > 0)
                    std::cout << "--> ";
            }
            std::cout << std::endl;
        }
        else
            std::cout << i << " : " << "null ..." << std::endl;
    }
}

main.cpp

#include "stdafx.h"
#include "hashtable.h"

int _tmain(int argc, _TCHAR* argv[])
{
    HashTable ht;
    int i = 1;
    for (; i < 8; ++i)
        ht.insert(i, i);

    std::cout << "show hash table" << std::endl;
    ht.show();

    return 0;
}

show hash table
0 : 6--> 3
1 : 7--> 4--> 1
2 : 5--> 2

链式存储
HashTable2.h
#pragma once

#include

struct Node
{
    Node() :  key(0), next(nullptr) {}
    Node(int k) : key(k), next(nullptr) {}

    struct Node *next;
    int key;
};

class HashTable
{
public:
    HashTable();
    ~HashTable();
    int hash(int key);
    Node* search(int key);
    int insert(int key);
    bool remove(int key);
    void show();

private:
    static const int SIZE;
    static const int M;
    Node** ht;
    int size;
};

const int HashTable::SIZE = 13;
const int HashTable::M = 13;

HashTable::HashTable()
{
    ht = new Node*[SIZE];
    for (int i = 0; i < SIZE; ++i)
        ht[i] = nullptr;
}

HashTable::~HashTable()
{
    if (ht != nullptr)
    {
        for (int i = 0; i < SIZE; ++i)
            if (ht[i] != nullptr)
            {
                delete ht[i];
                ht[i] = nullptr;
            }

        delete[] ht;
        ht = nullptr;
    }
}

int HashTable::hash(int key)
{
    return key % M;
}

int HashTable::insert(int key)
{
    int index = hash(key);
    Node* p = new Node(key);
    if (nullptr == p)
        return -1;
    
    p->next = ht[index];
    ht[index] = p;

    return 0;
}

Node* HashTable::search(int key)
{
    int index = hash(key);
    Node* p = ht[index];
    while (p != nullptr && p->key != key)
        p = p->next;

    return p;
}

bool HashTable::remove(int key)
{
    Node* p = search(key);
    if (p == nullptr)
        return false;

    int index = hash(key);
    // find precursor node of p
    Node* q = ht[index];
    while (q->next != p)
        q = q->next;

    q->next = p->next;

    delete p;
    p = nullptr;

    return true;
}

void HashTable::show()
{
    for (int i = 0; i < SIZE; ++i)
    {
        std::cout << i << " : ";
        Node* p = ht[i];
        if (p != nullptr)
        {
            while (p != nullptr)
            {
                std::cout << p->key;
                if (p->next != nullptr)
                    std::cout << " --> ";
                p = p->next;
            }
            std::cout << std::endl;
        }
        else
            std::cout << "Null..." << std::endl;
    }
}

main.cpp

#include "stdafx.h"
#include "HashTable2.h"

int main()
{
    HashTable ht;
    int arr[] = {19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79};
    for (int i = 0; i < sizeof(arr) / sizeof(int); ++i)
        ht.insert(arr[i]);
    ht.show();
    std::cout << "After delete 1" << std::endl;
    ht.remove(1);
    ht.show();

    return 0;
}

0 : Null...
1 : 79 --> 27 --> 1 --> 14
2 : Null...
3 : 55 --> 68
4 : Null...
5 : Null...
6 : 84 --> 19
7 : 20
8 : Null...
9 : Null...
10 : 10 --> 23
11 : 11
12 : Null...
After delete 1
0 : Null...
1 : 79 --> 27 --> 14
2 : Null...
3 : 55 --> 68
4 : Null...
5 : Null...
6 : 84 --> 19
7 : 20
8 : Null...
9 : Null...
10 : 10 --> 23
11 : 11
12 : Null...