I'm trying to write a hash map with a dynamic array that stores a set of pointers to a linked list struct. I've been running into some strange memory issues. It seems like there are pointers in my array that shouldn't be.
I get an error where even though the index that should be generated from the single insert I'm doing is 16, as I loop through the array, there are some non-zero items:
start
16 //(output of index from insert)
dumbtest //(get of nonexistent key)
0 // result of get of non-existent key
HashTable:
0 0x0--
0x0
1 0x0--
0x0
2 0xeb-- //Why is this not 0x0?
0xeb
I end up with an error: Thread 1: EXC_BAD_ACCESS (code=1, address=0x80000002c)
from this line in the string library:
_LIBCPP_INLINE_VISIBILITY
bool __is_long() const _NOEXCEPT
{return bool(__r_.first().__s.__size_ & __short_mask);}
I'm guessing that's the result of treating the junk in the array as a pointer and then trying to cast random bytes as the string of the "key" property.
Here is the class file
#include "hashtable.hpp"
using namespace std;
HashTable::HashTable()
{
this->length = 32;
this->buck = new LinkedList *[32];
};
unsigned int HashTable::hash(string key)
{
int hash = 7;
for (int i = 0; i < key.length(); i++) {
hash = hash*31 * key[i];
}
hash = hash % this->length;
return std::abs(hash);
}
int HashTable::find(string key)
{
int index = this->hash(key);
LinkedList *curr = this->buck[index];
while(curr != nullptr)
{
if(curr->key == key)
{
// std::cout << curr;
int val = curr->value;
return val;
}
curr = curr->next;
}
return 0;
}
void HashTable::output()
{
cout << "\nHashTable:\n";
for(int i = 0; i < this->length; i++)
{
LinkedList *curr = this->buck[i];
cout << "\t";
cout << i;
cout << "\t";
cout << curr;
cout << "--\n\t";
while (curr != nullptr){
cout << "\t";
cout << curr;
cout << ":";
cout << curr->key;
cout << ",";
cout << curr->value;
cout << ",";
cout << curr->next;
curr = curr->next;
}
cout << this->buck[i];
cout << "\n";
cout << "\n";
}
}
void HashTable::insert(string key, int value)
{
unsigned int index = this->hash(key);
cout << index;
LinkedList *curr = this->buck[index];
LinkedList *ins = new LinkedList{
key,
value,
NULL,
};
if (curr == nullptr){
this->buck[index] = ins;
}
else
{
while(curr->next != nullptr)
{
curr = curr->next;
}
curr->next = ins;
}
}
void HashTable::rehash()
{
this->length = 2 * this->length;
LinkedList** old = this->buck;
this->buck = new LinkedList* [this->length];
for (int i=0; i < this->length; i++)
{
LinkedList* curr = old[i];
while(curr != nullptr)
{
this->insert(curr->key, curr->value);
curr = curr->next;
}
}
}
And then my header
#ifndef hashtable_hpp
#define hashtable_hpp
#include <stdio.h>
#include <string>
#include <iostream>
struct LinkedList
{
std::string key;
int value;
LinkedList *next;
};
class HashTable
{
private:
int length;
LinkedList** buck;
unsigned int hash(std::string key);
void rehash();
public:
HashTable();
int find(std::string key);
void insert(std::string key, int value);
bool remove(std::string key);
void output();
};
#endif /* hashtable_hpp */
Here is the main file running it:
#include <stdio.h>
#include <string>
#include <iostream>
#include "hashtable/hashtable.hpp"
int main(int argc, const char * argv[])
{
std::cout << "start\n";
HashTable ht;
ht.insert("test", 3);
// ht.output();
std::cout << "\ndumbtest\n";
int dumbval = ht.find("testy");
std::cout << dumbval;
ht.output();
std::cout << "\ntest\n";
int val = ht.find("test");
std::cout << val;
std::cout << "\nend";
return 0;
}
Here's the stack trace:
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x80000002c)
* frame #0: 0x00000001000021bd algStudy`std::__1::basic_ostream<char, std::__1::char_traits<char> >& std::__1::operator<<<char, std::__1::char_traits<char>, std::__1::allocator<char> >(std::__1::basic_ostream<char, std::__1::char_traits<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&) [inlined] std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::__is_long(this="") const at string:1221
frame #1: 0x00000001000021bd algStudy`std::__1::basic_ostream<char, std::__1::char_traits<char> >& std::__1::operator<<<char, std::__1::char_traits<char>, std::__1::allocator<char> >(std::__1::basic_ostream<char, std::__1::char_traits<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&) [inlined] std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::__get_pointer(this="") const at string:1315
frame #2: 0x00000001000021bd algStudy`std::__1::basic_ostream<char, std::__1::char_traits<char> >& std::__1::operator<<<char, std::__1::char_traits<char>, std::__1::allocator<char> >(std::__1::basic_ostream<char, std::__1::char_traits<char> >&, std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> > const&) [inlined] std::__1::basic_string<char, std::__1::char_traits<char>, std::__1::allocator<char> >::data(this="") const at string:1129
frame #3: 0x00000001000021bd algStudy`std::__1::basic_ostream<char, std::__1::char_traits<char> >& std::__1::operator<<<char, std::__1::char_traits<char>, std::__1::allocator<char> >(__os=0x00007fff9b480660, __str="") at ostream:1047
frame #4: 0x0000000100002067 algStudy`HashTable::output(this=0x00007ffeefbff4c8) at hashtable.cpp:63
frame #5: 0x00000001000014c5 algStudy`main(argc=1, argv=0x00007ffeefbff5e8) at main.cpp:23
frame #6: 0x00007fff6388d015 libdyld.dylib`start + 1
frame #7: 0x00007fff6388d015 libdyld.dylib`start + 1
Any ideas?
