/
HashTable.cs
132 lines (115 loc) · 3.8 KB
/
HashTable.cs
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
namespace DataStructures.HashTable
{
using System;
using System.Collections;
using System.Linq;
using DataStructures.LinkedList;
using EnsureThat;
using MoreLinq;
public class HashTable<T> : IDynamicSet<T>
where T : IComparable<T>
{
private int length = 0;
private LinkedList<HashTableNode<T>>[] nodes = new LinkedList<HashTableNode<T>>[1];
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public System.Collections.Generic.IEnumerator<IDynamicSetNode<T>> GetEnumerator()
{
foreach (var linkedList in this.nodes)
{
if (linkedList != null)
{
foreach (var node in linkedList)
{
yield return node.Value;
}
}
}
}
public int Count()
{
return this.length;
}
public IDynamicSetNode<T> Insert(T value)
{
if (this.length == this.nodes.Length)
{
this.ExpandCapacity();
}
HashTableNode<T> node = new HashTableNode<T>(value, this);
this.InsertNode(node);
this.length++;
return node;
}
public void Delete(IDynamicSetNode<T> node)
{
this.ValidateNodeBelongsToThisSet(node);
HashTableNode<T> sNode = node as HashTableNode<T>;
this.RemoveNode(sNode);
sNode.RemoveFromList();
this.length--;
}
public IDynamicSetNode<T> Search(T value)
{
int index = this.Hash(value);
var linkedList = this.nodes[index];
if (linkedList == null)
{
return null;
}
else
{
return linkedList.FirstOrDefault(node => node.Value.Value.Equals(value))?.Value;
}
}
public IDynamicSetNode<T> Minimum()
{
return this.MinBy(i => i.Value).FirstOrDefault();
}
public IDynamicSetNode<T> Maximum()
{
return this.MaxBy(i => i.Value).FirstOrDefault();
}
private void ValidateNodeBelongsToThisSet(IDynamicSetNode<T> node)
{
HashTableNode<T> sNode = node as HashTableNode<T>;
EnsureArg.IsNotNull(sNode, nameof(node));
EnsureArg.IsTrue(sNode.Set == this, nameof(node), opts => opts.WithMessage("node does not belong to this table"));
}
private void ExpandCapacity()
{
var oldArray = this.nodes;
this.nodes = new LinkedList<HashTableNode<T>>[this.nodes.Length * 2];
foreach (LinkedList<HashTableNode<T>> linkedList in oldArray)
{
if (linkedList != null)
{
foreach (var node in linkedList)
{
this.InsertNode(node.Value);
}
}
}
}
private int Hash(T value)
{
return Math.Abs(value.GetHashCode()) % this.nodes.Length;
}
private void InsertNode(HashTableNode<T> node)
{
int index = this.Hash(node.Value);
this.nodes[index] = this.nodes[index] ?? new LinkedList<HashTableNode<T>>();
var linkedList = this.nodes[index];
var linkedListNode = linkedList.Insert(node) as LinkedListNode<HashTableNode<T>>;
node.LinkedListNode = linkedListNode;
}
private void RemoveNode(HashTableNode<T> node)
{
int index = this.Hash(node.Value);
var linkedList = this.nodes[index];
linkedList.Delete(node.LinkedListNode);
}
}
}