-
Notifications
You must be signed in to change notification settings - Fork 0
/
HashSet.cs
130 lines (100 loc) · 3.4 KB
/
HashSet.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
using Structures.Helper;
using Structures.Interface;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
namespace Structures.Hashing
{
internal class HashSet<T> : ITable<T>
{
private static readonly double _expandFactor = 0.75;
private static readonly int _defaultCapacity = 128;
private LinkedList<T>[] _hashTable;
public int Count { get; private set; }
public HashSet() : this(_defaultCapacity)
{ }
public HashSet(int initialCapacity) => _hashTable = new LinkedList<T>[initialCapacity];
public HashSet(IEnumerable<T> data) => BuildHashSet(data);
public ICollection<T> Find(T data)
{
var result = new LinkedList<T>();
var list = _hashTable[GetIndex(data.GetHashCode())];
if (list != null)
{
foreach (var item in list)
{
if (item.Equals(data))
{
result.AddLast(item);
break;
}
}
}
return result;
}
public void Insert(T data)
{
if (Find(data).Count > 0)
throw new ArgumentException("Cannot insert duplicate values");
if ((Count + 1) / (double)_hashTable.Length > _expandFactor)
Expand();
int index = GetIndex(data.GetHashCode());
if (_hashTable[index] == null)
_hashTable[index] = new LinkedList<T>();
_hashTable[index].AddLast(data);
Count++;
}
public void Update(T oldData, T newData)
{
Delete(oldData);
Insert(newData);
}
public void Delete(T data)
{
if (Find(data).Count == 0)
throw new ArgumentException("Data not found");
_hashTable[GetIndex(data.GetHashCode())].Remove(data);
Count--;
}
public IEnumerator<T> GetEnumerator()
{
if (Count == 0)
yield break;
for (int i = 0; i < _hashTable.Length; i++)
{
if (_hashTable[i] != null)
{
foreach (var item in _hashTable[i])
yield return item;
}
}
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
private int GetIndex(int hash) => hash % _hashTable.Length;
private void Expand()
{
var newTable = new LinkedList<T>[_hashTable.Length * 2];
foreach (var item in this)
{
var index = item.GetHashCode() % newTable.Length;
if (newTable[index] == null)
newTable[index] = new LinkedList<T>();
newTable[index].AddLast(item);
}
_hashTable = newTable;
}
private void BuildHashSet(IEnumerable<T> data)
{
_hashTable = new LinkedList<T>[data.Count().NextPowerOfTwo()];
foreach (var item in data)
{
int index = GetIndex(item.GetHashCode());
if (_hashTable[index] == null)
_hashTable[index] = new LinkedList<T>();
_hashTable[index].AddLast(item);
Count++;
}
}
}
}