nawk の再ハッシュ2010年01月09日 16時33分13秒

nawk のハッシュの実装が気になったので、調べてみた。特に気になっているのは再ハッシュの時期。

まずは、初期値。


#define   NSYMTAB 50      /* initial size of a symbol table */

最初に 50 個分の容量が確保されている。

次は、再ハッシュの時期を決める定数。


#define FULLTAB 2       /* rehash when table gets this x full */

現在の容量の二倍になった時に、再ハッシュを行なう。結構ゆっくりと待つみだいだ。

そして、再ハッシュ時の容量を決める定数。


#define GROWTAB 4       /* grow table by this factor */

四倍にする。しかし、既に衝突は容量の二倍になっているので、実際には元容量の二倍にするという事になる。

nawk も new awk とは名付けられた物の、既に世に出て二十五年も経っている。メモリの割り当て方がとても保守的だ。