title: Does a HashMap with string keys really have a lower time complexity than a Trie?
body: <p>Say I want to store a dictionary of strings and I want to know if some string exists or not. I can use a <a href="https://en.wikipedia.org/wiki/Trie" rel="nofollow" title="Trie">Trie</a> or a HashMap. The HashMap has a time complexity of O(1) with a high probability while the Trie in that case would have a time complexity of O(k) where k is the length of the string.</p>
  
  <p>Now my question is: Doesn't calculating the hash value of the string have a time complexity of O(k) thus making the complexity of the HashMap the same? If not, why?</p>
  
  <p>The way I see it is that a Trie here would have lower time complexity than a HashMap for looking up a string since the HashMap -in addition to calculating the hash value- might hit collisions. Am I missing something?</p>
  
  <p>Update: 
  Which data structure would you use to optimize for speed when constructing a dictionary?</p>