1. array, linked list & hashing

Evening folks.

I've done a bit of re-search on array vs linked list.

* Arrays has uick random access
* Arrays are static, resize takes a long time
* Arrays have a power search algorithm (binary)
* Arrays are slow at adding and removing elements

* Linked list is dynamic so size isnt a problem
* Linked list has slow random access

Im typing this by memory so I hope I havnt missed anything major. Anyway, I've been reading a bit about using hashing to store data. I was wondering how hashing differs from the above two, what are the pros and cons ?

Appreciate any help.

2. hashing

hashing can work with arrays or linked lists. Usually it is done with linked lists. Hashing has the advantage of being very fast when using it for searching for words. A word is assigned a numeric value based on its contents. Sometimes a combination of arrays and linked lists are used when hashing. Say for example you have an array structs of 1000 elements. You go on assigning values to the words based on their contents. When you do this it is possible that you have a collision because two different words can end up with the same value say for example "dog" and "cat" both end up with the value 100. You would store the first word that you run into into array[100]. The second word with the same value can be linked to array[100]. Therefore when you search for the word cat or dog you would end up in array[100] but because each of the elements is a linked list you would have to walk the list to see if it exists in the element. In essence many times a hash list is an array of linked lists. One linked list in each element of the array.

3. So what your basiclly saying is that hashing can be a combination of arrays and linked list.

4. It usually is, yes.
Say that you're storing 5-digit numbers. In a linked list you'd have to traverse the whole list in the worst case to find that number. In an array, you could find it directly but the array would be incredibly huge.

In this case you could make a hash table. basically, it is an array of linked lists. Say that the first 2 digits in the number specify an element in the array, and that the rest of the digits are stored in a linked list in that element of the array.
This would decrease the search time since the linked list is 100 times shorter (assuming the numbers are evenly distributed, that's why you need a good hashing function. There is no gain if all numbers is placed in the same array element) while the array isn't too big.