Started by jamespetts, February 18, 2014, 12:46:30 AM
0 Members and 1 Guest are viewing this topic.
Quote from: Ters on February 18, 2014, 05:46:31 AM In any case, the complexity of a hashtable search is O(n), just like a straight arrays, but unlike B-trees which are O(log n). Although both normal arrays and hashtables are O(n), the latter should be faster. O(n) just means that an array or hashtable that's twice as big is also twice as slow.
QuoteA hashtable should be O(1) (constant look-up time), that's the whole point; if it isn't, you need more bins.
Quote from: Dwachs on February 18, 2014, 08:30:37 AMSimutrans standard does use the hashtables only in non-performance critical parts of the code (retrieving objects by name, translation of text snippets).
Quote from: MCollett on February 18, 2014, 06:12:51 AMAnd while a tree (of any type, not just B-trees) should indeed be O(lg n), so should binary search in a sorted array.
Quote from: Ters on February 19, 2014, 06:32:13 AMAnd if you know how many elements the hashtable will contain, even just roughly, tell it so up front, because changing the number of buckets is really O(n), both best case and worst case, as far as I can tell.
QuoteSTL actually don't have a hashtable.
Quote from: ArthurDenture on February 24, 2014, 02:17:36 AMTo be pedantic, STL certainly does have a hashtable, but the C++ Standard Library (before C++11) does not. Citation: http://stackoverflow.com/a/5908859/483595
Quote from: ArthurDenture on February 24, 2014, 02:17:36 AMAre there compilers targeted by Simutrans that do not provide std::hash_map?