title: Memory efficiency: HashMap versus Array
body: <p>I was thinking about the following situation: I want to count the occurrence of characters in a string (for example for a permutation check). </p>
  
  <p>One way to do it would be to allocate an array with 256 integers (I assume that the characters are UTF-8), to fill it with zeros and then to go through the string and increment the integers on the array positions corresponding to the int value of the chars.  </p>
  
  <p>However, for this approach, you would have to allocate a 256 array each time, even when the analyzed string is very short (and consequently uses only a small part of the array).</p>
  
  <p>An other approach would be to use a Character to Integer HashTable and to store a number for each encountered char. This way, you only would have keys for chars that actually are in the string.</p>
  
  <p>As my understanding of the HashTable is rather theoretic and I do not really know how it is implemented in Java my question is: Which of the two approaches would be more memory efficient? </p>
  
  <p>Edit:</p>
  
  <p>During the discussion of this question (thank you for your answers everyone) I did realize that I had a very fuzzy understanding of the nature of UTF-8. After some searching, I have found <a href="http://www.youtube.com/watch?v=MijmeoH9LT4" rel="nofollow">this great video</a> that I want to share, in case someone has the same problem. </p>