Simple hash table with vector

Question

As i understood correctly , implementing hash table , is calculating index based on inputed string , and returning it directly making it simple key - value storage.

So simple hash function could look something like

int hash( string name ){

    int index = 0;
    int hash = 0;
    for ( int i = 0; i < name.length() ;i++){
        hash += (int)name[i];
    }
    index = sizeOfArray % hash;
}

SizeOfArray is array of pointers with predefined size. If this index does not exists it creates it. But how i implement it with vectors?

Vector does not have predefined size. An they grow automaticly. So calling sizeOfArray % hash will change everytim vector will grow.

What is logic behind has tables? Whats the best method to calculate index even with growing vector / array?

Why not simply use an array of string *? And, since there may be collisions, you're better of using an array of linked lists (or vectors) of string, since multiple strings have to be attachable to one hash key. By the way, maybe you make this just to learn from, which is very useful. But hash keys are the basis of many STL datastructures which come with your compiler. — Jacques de Hooge
– Jacques de Hooge, Commented Mar 26, 2016 at 9:49
Learning about hash-tables are a good idea, but don't implement your own for anything but learning purposes, not when there's std::unordered_map. — Some programmer dude
– Some programmer dude, Commented Mar 26, 2016 at 9:52
You can tell a vector to be a specific size and they do not grow automatically unless you call a function that makes them grow. — Galik
– Galik, Commented Mar 26, 2016 at 9:55
Also, your index calculation is wrong, it should the the other way around: hash % sizeOfArray. — Some programmer dude
– Some programmer dude, Commented Mar 26, 2016 at 9:58
Linear hashing doesn't result in linear complexity for the lookup, it's still constant time. — HenryLee
– HenryLee, Commented Mar 26, 2016 at 10:19

Anmol Singh Jaggi · Accepted Answer · 2016-03-26 10:56:13Z

1

You can use a vector<list<string>> as the underlying data structure for the hash table.
Also, you got the index calculation wrong; instead of sizeOfArray % hash, it should be the other way round.

vector<list<string>> hash_table;
const size_t hash_table_size = 100;
hash_table.resize(hash_table_size);

int hash( string name ){
    int index = 0;
    int hash = 0;
    for ( int i = 0; i < name.length() ;i++){
        hash += (int)name[i];
    }

    index = hash % hash_table.size();
    hash_table[index].push_back(name);
}

answered Mar 26, 2016 at 10:56

Anmol Singh Jaggi

8,6964 gold badges40 silver badges82 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Tony Delroy Over a year ago

The OP should find this helpful, but - nitpicking - it shouldn't be the hash function actually inserting data in the table: a seperate insert function that calls hash ought to do that (and likely also do the % hash_table.size()). Further, you shouldn't push_back to the bucket without checking whether the name already appears therein. But, the OP can sort those things out I'm sure....

Collectives™ on Stack Overflow

Simple hash table with vector

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related