{"action":"created","issue":{"url":"https://api.github.com/repos/waynewbishop/SwiftStructures/issues/22","labels_url":"https://api.github.com/repos/waynewbishop/SwiftStructures/issues/22/labels{/name}","comments_url":"https://api.github.com/repos/waynewbishop/SwiftStructures/issues/22/comments","events_url":"https://api.github.com/repos/waynewbishop/SwiftStructures/issues/22/events","html_url":"https://github.com/waynewbishop/SwiftStructures/issues/22","id":60314787,"number":22,"title":"Hash table should be implemented as Dictionary","user":{"login":"skywinder","id":3356474,"avatar_url":"https://avatars.githubusercontent.com/u/3356474?v=3","gravatar_id":"","url":"https://api.github.com/users/skywinder","html_url":"https://github.com/skywinder","followers_url":"https://api.github.com/users/skywinder/followers","following_url":"https://api.github.com/users/skywinder/following{/other_user}","gists_url":"https://api.github.com/users/skywinder/gists{/gist_id}","starred_url":"https://api.github.com/users/skywinder/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/skywinder/subscriptions","organizations_url":"https://api.github.com/users/skywinder/orgs","repos_url":"https://api.github.com/users/skywinder/repos","events_url":"https://api.github.com/users/skywinder/events{/privacy}","received_events_url":"https://api.github.com/users/skywinder/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-03-09T09:01:08Z","updated_at":"2015-03-09T18:27:51Z","closed_at":null,"body":"The main advantage of has table is quick access to elemets:\r\n\r\nTime complexity for hash tables (from wiki):\r\n\r\n Type | Average | Worst case\r\n------------ | ------------- | -------------\r\nSpace | O(n) | O(n)\r\nSearch | O(1) | O(n)\r\nInsert | O(1) | O(n)\r\nDelete | O(1) | O(n)\r\n\r\nSince your has 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.\r\nFor correct implementation of this structure hash table should be implemented as Dictionary"},"comment":{"url":"https://api.github.com/repos/waynewbishop/SwiftStructures/issues/comments/77913353","html_url":"https://github.com/waynewbishop/SwiftStructures/issues/22#issuecomment-77913353","issue_url":"https://api.github.com/repos/waynewbishop/SwiftStructures/issues/22","id":77913353,"user":{"login":"waynewbishop","id":128404,"avatar_url":"https://avatars.githubusercontent.com/u/128404?v=3","gravatar_id":"","url":"https://api.github.com/users/waynewbishop","html_url":"https://github.com/waynewbishop","followers_url":"https://api.github.com/users/waynewbishop/followers","following_url":"https://api.github.com/users/waynewbishop/following{/other_user}","gists_url":"https://api.github.com/users/waynewbishop/gists{/gist_id}","starred_url":"https://api.github.com/users/waynewbishop/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/waynewbishop/subscriptions","organizations_url":"https://api.github.com/users/waynewbishop/orgs","repos_url":"https://api.github.com/users/waynewbishop/repos","events_url":"https://api.github.com/users/waynewbishop/events{/privacy}","received_events_url":"https://api.github.com/users/waynewbishop/received_events","type":"User","site_admin":false},"created_at":"2015-03-09T18:27:51Z","updated_at":"2015-03-09T18:27:51Z","body":"Hi Petr;\r\n\r\nThanks 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 function \"good enough\" to avoid collisions in the first place ```O(1)```. My full documentation can also be found at www.waynewbishop.com/swift/hashtables.\r\n\r\nIf there's something else you'd like to see, feel free to submit a pull request and I can review.\r\n\r\nThanks;\r\n\r\n```\r\n  //iterate through the list of items to find a match\r\n\r\n        else {\r\n            \r\n            var current: HashNode! = buckets[hashindex]\r\n            \r\n            while (current != nil) {\r\n                \r\n                var hashName: String! = current.firstname + current.lastname\r\n                \r\n                if (hashName == fullname) {\r\n                    println(\"\\(current.firstname) \\(current.lastname) found in hash table..\")\r\n                    return true\r\n                }\r\n                \r\n                \r\n                println(\"searching for word through chained list..\")\r\n                current = current.next\r\n                \r\n                \r\n             } //end while\r\n            \r\n            \r\n        } //end if\r\n```"}}