- Home /
Problem with HashSet
So I'm having a problem with the implementation of HashSet getting stuck in an endless loop working through it's internal implementation which uses a linked list. For some reason the list is getting linked back to itself after a resize operation or a series of removal and resize operations.
Basically it jams up in anywhere the linked list is used. E.g. this becomes an endless loop:
bool SlotsContainsAt(int index, int hash, T item)
{
int current = table[index] - 1;
while (current != NO_SLOT)
{
Link link = links[current];
if (link.HashCode == hash && ((hash == HASH_FLAG && (item == null || null == slots[current])) ? (item == null && null == slots[current]) : comparer.Equals(item, slots[current])))
return true;
current = link.Next;
}
return false;
}
So I believe this only happens after a resize operation or a significant number of removals. I can't work out what's wrong though - I've built my own version from the Mono source and added some debugging, here's the original:
void Resize()
{
int newSize = HashPrimeNumbers.ToPrime((table.Length << 1) | 1);
// allocate new hash table and link slots array
var newTable = new int[newSize];
var newLinks = new Link[newSize];
for (int i = 0; i < table.Length; i++)
{
int current = table[i] - 1;
while (current != NO_SLOT)
{
int hashCode = newLinks[current].HashCode = GetItemHashCode(slots[current]);
int index = (hashCode & int.MaxValue) % newSize;
newLinks[current].Next = newTable[index] - 1;
newTable[index] = current + 1;
current = links[current].Next;
}
}
table = newTable;
links = newLinks;
// allocate new data slots, copy data
var newSlots = new T[newSize];
Array.Copy(slots, 0, newSlots, 0, touched);
slots = newSlots;
threshold = (int)(newSize * DEFAULT_LOAD_FACTOR);
}
And here's my debug version that does show that it is trying to link to itself just before my endless loop happens:
void Resize()
{
int newSize = HashPrimeNumbers.ToPrime((table.Length << 1) | 1);
// allocate new hash table and link slots array
var newTable = new int[newSize];
var newLinks = new Link[newSize];
for (int i = 0; i < table.Length; i++)
{
int current = table[i] - 1;
while (current != NO_SLOT)
{
int hashCode = links[current].HashCode;
int index = (hashCode & int.MaxValue) % newSize;
if (newTable[index] != current+1)
{
newLinks[current].Next = newTable[index] - 1; //NO_SLOT the first time
}
else
{
UnityEngine.Debug.LogError("HashSet::Trying to link to self");
}
newTable[index] = current + 1;
current = links[current].Next;
}
}
table = newTable;
links = newLinks;
// allocate new data slots, copy data
var newSlots = new T[newSize];
Array.Copy(slots, 0, newSlots, 0, touched);
slots = newSlots;
threshold = (int)(newSize * DEFAULT_LOAD_FACTOR);
}
@Bunny83 - sounds like one for you if you can spare the time!
Also note, even though I'm trying to break the endless loop with that modified code, I don't seem to be successful - so perhaps something else is screwed up. I can only think that this would imply multiple entries in the slots list pointing to different items, or the hashcodes messing up somewhere.
Answer by whydoidoit · Aug 23, 2013 at 02:39 PM
Ah turned out to be a multithreading issue that only occurs in the Editor.