算法数据结构

【模板】无重哈希映射

字数统计: 1.5k字   |   阅读时长: 8分
,

摘要: 开散列表与闭散列表的哈希映射，代码模板

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

哈希映射是将哈希集合中的每个节点加一个数据的字段，其余部分与哈希集合基本一样。支持集合增删改查的哈希表理论也与哈希集合一样。参考文章 【模板】哈希集合。

对于无重哈希映射，核心的增删改查操作如下：

  • insert(k, v)：若存在 k，则更新 v，否则插入新节点
  • find(k): 所存在 k，返回对应的 v，否则返回给定值
  • remove(k): 若存在 k ，删除节点

本文基于闭散列表与开散列表实现这些操作，形成代码模板。并用 706. 设计哈希映射 来测试。

哈希映射在哈希集合基础上的变化

闭散列表

闭散列表哈希集合的节点定义如下：

1
2
3
4
5
6
7
8
9
10
11
struct Node
{
    HashType data;
    int state;
    // 0: Empty  -1: deleted
    // >0: active
    Node()
    {
        state = 0;
    }
};

由于闭散列表需要标识节点状态，空和被删是两种不同状态。

对于哈希映射，在节点中加一个值的字段。对于无重映射，用变量 item。

闭散列表哈希映射的节点定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
struct Node
{
    HashType data;
    ValueType item; 
    int state;
    // 0: Empty  -1: deleted
    // >0: active
    Node()
    {
        state = 0;
    }
};

开散列表

哈希集合的节点定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct Node
{
    HashType data;
    Node *next;
    Node(const HashType &x)
    {
        data = x;
        next = nullptr;
    }
    Node()
    {
        next = nullptr;
    }
};

开散列表不需要标识节点状态。

对于哈希映射，在节点中加一个值的字段。无重映射用变量 item。

闭散列表哈希映射的节点定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Node
{
    HashType data;
    ValueType item;
    Node *next;
    Node(const HashType& x, cosnt ValueType& v)
    {
        data = x;
        item = v;
        next = nullptr;
    }
    Node()
    {
        next = nullptr;
    }
};

代码模板：闭散列表无重哈希映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
const int INF = 1e9;
typedef int HashType;
typedef int ValueType;
const ValueType VALUENULL = -1;

class CloseHashTable
{
private:
    struct Node
    {
        HashType data;
        ValueType item;
        int state;
        // 0: Empty  -1: deleted
        // >0: cnt / active
        Node()
        {
            state = 0;
        }
    };

    Node *arraytable;
    int sizetable;
    int (*key)(const HashType& x); // 将 key 变成一个整数，如果 key 本身是整数直接返回
    const double A = 0.6180339887;

    static int defaultKey(const int &k)
    {
        return k;
    }

    int hash1(const HashType& x) const
    {
        if(key(x) < 0)
            return key(x) % sizetable;
        return (key(x) + INF) % sizetable;
    }

    int hash2(const HashType& x) const
    {
        double d;
        if(key(x) < 0)
            d = (key(x) + INF) * A;
        else
            d = (key(x)) * A;
        return (int)(sizetable * (d - (int)d));
    }

public:
    CloseHashTable(int length=20011, int (*f)(const HashType &x)=defaultKey)
    {
        sizetable = length;
        arraytable = new Node[sizetable];
        key = f;
    }

    ~CloseHashTable()
    {
        delete [] arraytable;
    }

    ValueType findx(const HashType& x) const;
    bool insertx(const HashType& x, const ValueType& v);
    bool removex(const HashType& x);
    void rehash();
};

ValueType CloseHashTable::findx(const HashType &x) const
{
    int initPos = hash2(x);
    int pos = initPos;

    do
    {
        if(arraytable[pos].state == 0)
            return VALUENULL;
        if(arraytable[pos].state > 0 && arraytable[pos].data == x)
            return arraytable[pos].item;
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return VALUENULL;
}

bool CloseHashTable::insertx(const HashType& x, const ValueType& v)
{
    int initPos = hash2(x);
    int pos = initPos;

    do{
        if(arraytable[pos].state <= 0)
        {
            arraytable[pos].data = x;
            arraytable[pos].item = v;
            arraytable[pos].state = 1;
            return true;
        }
        else if(arraytable[pos].state > 0 && arraytable[pos].data == x)
        {
            // 有重映射将用新值覆盖 item 改为将新值插入 items
            arraytable[pos].item = v;
            return true;
        }
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return false;
}

bool CloseHashTable::removex(const HashType &x)
{
    int initPos = hash2(x);
    int pos = initPos;

    do
    {
        if(arraytable[pos].state == 0)
            return false;
        if(arraytable[pos].state > 0 && arraytable[pos].data == x)
        {
            // 有重映射改为将节点下的所有 item 删掉，将 arraytable[pos].state 改为 -1 后返回
            arraytable[pos].state = -1;
            return true;
        }
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return false;
}

void CloseHashTable::rehash()
{
    Node *tmp = arraytable;
    arraytable = new Node[sizetable * 2];

    for(int i = 0; i < sizetable; ++i)
        if(tmp[i].state > 0)
            insertx(tmp[i].data, tmp[i].item);

    sizetable *= 2;
    delete [] tmp;
}

代码模板：开散列表无重哈希映射

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
class OpenHashTable
{
private:
    struct Node
    {
        HashType data;
        ValueType item;
        Node *next;
        Node(const HashType &x, const ValueType& v)
        {
            data = x;
            item = v;
            next = nullptr;
        }
        Node()
        {
            next = nullptr;
        }
    };

    Node **arraytable;
    int sizetable;
    int (*key)(const HashType &x);
    const double A = 0.6180339887;

    static int defaultKey(const int &k)
    {
        return k;
    }

    int hash1(const HashType& x) const
    {
        if(key(x) < 0)
            return (key(x) + INF) % sizetable;
        return key(x) % sizetable;
    }

    int hash2(const HashType& x) const
    {
        double d;
        if(key(x) < 0)
            d = (key(x) + INF) * A;
        else
            d = (key(x)) * A;
        return (int)(sizetable * (d - (int)d));
    }

public:
    OpenHashTable(int length = 20011, int (*f)(const HashType &x) = defaultKey)
    {
        sizetable = length;
        arraytable = new Node*[sizetable];
        key = f;
        for(int i = 0; i < sizetable; ++i)
        {
            arraytable[i] = new Node;
        }
    }

    ~OpenHashTable()
    {
        Node *p,*q;
        for(int i = 0; i < sizetable; ++i)
        {
            p = arraytable[i];
            // 头删
            do
            {
                q = p -> next;
                delete p;
                p = q;
            }while(p != nullptr);
        }
        delete [] arraytable;
    }

    ValueType findx(const HashType &x) const
    {
        int pos = hash2(x);
        Node *p = arraytable[pos];
        while(p -> next != nullptr && (p -> next -> data != x))
            p = p -> next;
        if(p -> next != nullptr)
            return p -> next -> item;
        else
            return VALUENULL;
    }

    bool insertx(const HashType& x, const ValueType& v)
    {
        int pos = hash2(x);
        Node *p = arraytable[pos] -> next;
        while(p != nullptr && p -> data != x)
            p = p -> next;
        // 没找到就头插
        if(p == nullptr)
        {
            p = new Node(x, v);
            p -> next = arraytable[pos] -> next;
            arraytable[pos] -> next = p;
            return true;
        }
        else
        {
            p -> item = v;
            return true;
        }
        return false;
    }

    bool removex(const HashType &x)
    {
        int pos = hash2(x);
        Node *p = arraytable[pos];
        Node *q;
        while(p -> next != nullptr && p -> next -> data != x)
            p = p -> next;
        if(p -> next == nullptr)
            return false;
        else
        {
            // 如果是无重集合，直接删 p -> next 即可
            q = p -> next;
            p -> next = q -> next;
            delete q;
            return true;
        }
    }
};

代码测试: 706. 设计哈希映射

下面代码中 CloseHashTable 可以直接改为 OpenHashTable。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class MyHashMap {
public:
    /** Initialize your data structure here. */
    MyHashMap() {
        mapping = new CloseHashTable(N);
    }

    /** value will always be non-negative. */
    void put(int key, int value) {
        mapping -> insertx(key, value);
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        return mapping -> findx(key);
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        mapping -> removex(key);
    }

private:
    const int N = 20011;
    CloseHashTable *mapping;
};
Share