Hash Tables

Hash tables are used when you need to find things using non-sequential (or just non-integer) keys - strings, for example, or very large ranges of integers. They''re usually used to implement dictionaries/associative arrays because they have constant time random access.

Linked lists are used when items are inserted or deleted in the middle more than the at the ends, or iterators need to remain valid at all times (except after they''re erased, of course).

Don''t think I''ve ever used a hash table for practical purposes, but as far as linked lists go, use them for holding elements that are accessed sequentially and when there are many removals and insertions. The main plus of a linked list is constant time insertion and removal. Also if you are using STL, with a linked list your iterators are not invalidated on removal, unlike a vector or a queue.

An example is a partical system using a custom allocator(to avoid lots of fragmentation of the heap) or an entity system again with a custom allocator.

You dont want to use a linked list when you have to search.

A hash table has constant time lookup. They''re not particularly suited to listing its entire contents, so it probably wouldn''t be particularly suited to use as a character inventory. A sorted list would probably be a better solution in that case.

Pathfinding

Hashtables are use frequently in turn based games, such as chess. A typical chess playing algorithm will keep a transposition table of all of the board information that has already been searched(top-down dynamic programming ie memoization). These transposition tables are generally implemented as hash tables due to the extremely fast O(1)(usually) access time, although some other operations take a bit more time...

quote:

---

Original post by MARS_999
What would one use Hash tables for? I see the only use is for databases? I could see them being used for character inventory in a RPG.

---

Right. A hash table is used to store data. It''s no different, in that respect, than a linked list, binary tree (avl, rb, etc), or a plain old array. That''s why these data structures are referred to as "containers" - they contain data.

The difference between all these containers, is generally the speed of which you can add/remove/search for items.

I suspect nearly all compilers/interpreters uses hash tables for symbol lookup - i.e. given a symbol "foo" what is its data (or, where is the data located in memory?)

quote:

---

Original post by MARS_999
Also what does everyone here use linked list for?

---

I''ve been playing with a very basic Scheme-Like interpreter I''m writing. I use linked lists extensively for holding the data of the program. Why? Because of constant time insertion, and constant time deletion* - plus, all data (including your program) is nothing but a list


* constant time insertion/deletion simply means that the cost(number of operations) of deleting/adding an item is not a function of the number of items in the list.

quote:

---

Original post by g00ch

quote:

---

Original post by MARS_999
What would one use Hash tables for? I see the only use is for databases? I could see them being used for character inventory in a RPG.

---

Right. A hash table is used to store data. It''s no different, in that respect, than a linked list, binary tree (avl, rb, etc), or a plain old array. That''s why these data structures are referred to as "containers" - they contain data.

The difference between all these containers, is generally the speed of which you can add/remove/search for items.

I suspect nearly all compilers/interpreters uses hash tables for symbol lookup - i.e. given a symbol "foo" what is its data (or, where is the data located in memory?)

quote:

---

Original post by MARS_999
Also what does everyone here use linked list for?

---

I''ve been playing with a very basic Scheme-Like interpreter I''m writing. I use linked lists extensively for holding the data of the program. Why? Because of constant time insertion, and constant time deletion* - plus, all data (including your program) is nothing but a list


* constant time insertion/deletion simply means that the cost(number of operations) of deleting/adding an item is not a function of the number of items in the list.

---

So to add or delete an item is constant in time costs. So there is no guessing how long it takes to add or delete some item, so you can count on it taking .1ms or something? Thanks

the actual removal may be constant, but you still have to find the node you want to remove.

quote:

---

So to add or delete an item is constant in time costs. So there is no guessing how long it takes to add or delete some item, so you can count on it taking .1ms or something? Thanks

---

check here

Hash tables are very powerful ways of storing your data. There are countless ways to use them. Basically, whenever you have a collection of items and you want to be able to pick one particular item out of that list, a hash table is probably a good way to go. Basically, they''re the same as a linked list except the average complexity of looking up an item is O(1) instead of O(n). (although worst case is still O(n)) i could go on for hours about good data sets for hash tables. you just have to be creative with your hash functions. your question is like asking ''why use heapsort instead of bubblesort'' or ''why use binary search instead of linear search?''.

I use hashmaps in my resource manager to create a filename -> resource object mapping, so when we need to load a resource by filename, we can check the hashmap to see if already exists and share it.

I prefer vectors and chunked lists (deques) over linked lists for most things because they''re a lot nicer on CPU cache. I use linked lists for the free list when I''m creating memory pools... but thats about it.