配列に対するindexとHashのアクセス時間が違いすぎてやばい

Rubyでn-gramの計算をするためにプログラムを書いていたが、全くスピードが出ず悩んでいたら、配列に対してindexでアクセスしていたところを配列ではなくてHashで組んだら改善された。

http://d.hatena.ne.jp/A_Koide0519/20111002/1317535717:前回に比べて、メモリの使い方とか何とか自分なりに工夫したつもり。

今までは

VecC = []
k = 0
if VecC.index(word) == nil
   VecC[k] = word
   k+=1
end

みたいなことをしていた部分を

wordlist = Hash.new()
size = 0
if wordlist.key?(word) == false
   wordlist.store(word,wordlist.size+1)
end

みたいにした。
やっていることは、文字列wordがリストになかったら登録するっていうことだけど、スピードは後者が圧倒的。
何となく後者がO(1)になるような気がするんだけど、前者がなぜ遅いのかちゃんと理由を知っておいた方がよさそうなので、いろいろ検索をかけてみたものの、よくわからない。
Rubyの偉い人に教えてもらいたいところ。