Thread: array, linked list & hashing

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    291

    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 very quick to add and remove 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. #2
    Registered User
    Join Date
    Aug 2001
    Posts
    223

    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.
    zMan

  3. #3
    Registered User
    Join Date
    Oct 2002
    Posts
    291
    So what your basiclly saying is that hashing can be a combination of arrays and linked list.

  4. #4
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    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.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  5. #5
    Registered User
    Join Date
    Oct 2002
    Posts
    291
    Thanks for your reply Magos.

    So I guess arrays with linked list (chaining hashing) is the prefered choice and not double hashing or hashing with linear probing.

    I've read a few articles and tutorials on hashing but their coverage of how to make a good hash function is not great. Can anyone recommend a thorough guide\tutorial.

  6. #6
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    One clarification:
    * Linked list has slow random access
    Linked lists have NO random access.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  2. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  3. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  4. linked list inside array of structs- Syntax question
    By rasmith1955 in forum C Programming
    Replies: 14
    Last Post: 02-28-2005, 05:16 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM