Special

Introducing the “Welcome to Xojo” Bundle!

New to Xojo and looking for guidance? We've put together a terrific bundle to welcome you! Xojo Bundle

This bundle includes six back issues of the magazine -- all of year 21 in printed book and digital formats -- plus a one-year subscription (beginning with 22.1) so you'll be learning all about Xojo for the next year. It's the perfect way to get started programming with Xojo. And you save as much as $35 over the non-bundle price!

This offer is only available for a limited time as supplies are limited, so hurry today and order this special bundle before the offer goes away!

Article Preview


Buy Now

Issue 10.3 ('Hashes')
Instant purchase and download via GumRoad!

FEATURE

When Hashes Collide

Basic strategies for handling hash collisions

Issue: 10.3 (March/April 2012)
Author: JC Cruz
Author Bio: JC is a freelance engineering writer based in British Columbia. He frequently contributes articles to MacTech and RealStudio Developer. He also covers advanced ObjC and iOS topics for Dr Dobbs Journal. Away from the writing pile, JC spends quality time with his foster nephew, as a proper uncle should. He can be reached at anarakisware@gmail.com.
Article Description: No description available.
Article Length (in bytes): 34,277
Starting Page Number: 39
Article Number: 10308
Related Web Link(s):

http://en.wikipedia.org/wiki/Hash_table
http://en.wikipedia.org/wiki/Linear_probing
http://en.wikipedia.org/wiki/Quadratic_probing
http://en.wikipedia.org/wiki/Double_hashing
http://en.wikipedia.org/wiki/Linked_list
http://www.sparknotes.com/cs/searching/hashtables/summary.html
http://eternallyconfuzzled.com/tuts/dataMsguctures/jsw
http://www.cs.auckland.ac.nz/~jmor159/PLDS210/hash_tables.html

Excerpt of article text...

Regardless of what algorithm is used, all hash functions will suffer at least one collision. So today, we take a close look at a hash collision and understand why it happens. Then we study some basic strategies to manage a collision.

Collection of Hash

In a previous article (RSD 8.4, May/June 2010), we studied how a general-purpose hash function reduces a data item into an integer value. We learned the traits of a good hash function and ways to test for those traits.

There are many ways we can use hash functions, too many to be listed in detail. One use is to mark each data item stored in a collection. Each item gets a unique id, making it easy for us to do queries, inserts and edits. Again, there are many types of collection structures, but the one we will focus on is the hash table.

The hash table

A hash table arranges its data as "columns" of keys and values (Figure 1). In the value column are the data items, in the keys column the hashes for each item. The key column is always sorted, while the value column is not.

...End of Excerpt. Please purchase the magazine to read the full article.