title: Performance of Arrays and Hashes in Ruby
body: <p>I have a program that will store many instances of one class, let's say up to 10.000 or more. The class instances have several properties that I need from time to time, but their most important one is the ID.</p>
  
  <pre><code>class Document
    attr_accessor :id
    def ==(document)
      document.id == self.id
    end
  end
  </code></pre>
  
  <p>Now, what is the fastest way of storing thousands of these objects?</p>
  
  <p>I used to put them all into an array of Documents:</p>
  
  <pre><code>documents = Array.new
  documents &lt;&lt; Document.new
  # etc
  </code></pre>
  
  <p>Now an alternative would be to store them in a Hash:</p>
  
  <pre><code>documents = Hash.new
  doc = Document.new
  documents[doc.id] = doc
  # etc
  </code></pre>
  
  <p>In my application, I mostly need to find out whether a document exists at all. Is the Hash's <code>has_key?</code> function significantly faster than a linear search of the Array and the comparison of <code>Document</code> objects? Are both within <em>O(n)</em> or is <code>has_key?</code> even <em>O(1)</em>. Will I see the difference?</p>
  
  <p>Also, sometimes I need to add Documents when it is already existing. When I use an Array, I would have to check with <code>include?</code> before, when I use a Hash, I'd just use <code>has_key?</code> again. Same question as above.</p>
  
  <p>What are your thoughts? What is the fastest method of storing large amounts of data when 90% of the time I only need to know whether the ID exists (not the object itself!)</p>