Hash table should be implemented as Dictionary

[skywinder]

The main advantage of hash table is quick access to elemets:

Time complexity for hash tables (from wiki):

Type	Average	Worst case
Space	O(n)	O(n)
Search	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)

Since your hash table implemented as loop in array - the average complexity of search is O(n), not O(1), that not fit this time complexity requirements of hash tables.
For correct implementation of this structure hash table should be implemented as Dictionary

[waynewbishop]

Hi Petr;

Thanks for posting your question about hash tables. As you've noted, the findWord method is based on using separate chaining for handling collisions. In my case, I've chosen to handle collisions with a linked list. While its possible one may have to traverse an entire chained list to find a word O(n), the ideal situation would be create a hash algorithm "good enough" to avoid collisions in the first place O(1). My full documentation can also be found at www.waynewbishop.com/swift/hashtables.

If there's something else you'd like to see, feel free to submit a pull request and I can review.

Thanks;

  //iterate through the list of items to find a match

        else {

            var current: HashNode! = buckets[hashindex]

            while (current != nil) {

                var hashName: String! = current.firstname + current.lastname

                if (hashName == fullname) {
                    println("\(current.firstname) \(current.lastname) found in hash table..")
                    return true
                }


                println("searching for word through chained list..")
                current = current.next


             } //end while


        } //end if

[skywinder]

Yes, I just mention it here, to clarify some specific aspects of hash table. Probably I will PR new algorithm later. Anyway, thanks for great project!

[waynewbishop]

Hi Petr;

Sounds good. You've raised some good points that would probably help others. I'll see about extending the corresponding the hash tables essay with these notes.

[waynewbishop]

These comments will included in the book when it goes to print.