hash - a_ogawa

mysqlのハッシュテーブルは、PostgreSQLと同じリニアハッシュ・アルゴリズムを使用している。
(PostgreSQLのハッシュテーブル:http://www.hi-ho.ne.jp/a_ogawa/document/pg_dynahash.pdf)
PostgreSQLと違う点。
- ハッシュテーブルにデータを登録するたびに、テーブルを拡張する。 (データ数 = Bucket数になる)
- ハッシュ番地が衝突したときは、データを空いているBucketに登録して、線形リストでリンクする。

typedef struct st_hash {
  uint key_offset,key_length;       /* Length of key if const length */
  uint records,blength,current_record;
  uint flags;
  DYNAMIC_ARRAY array;              /* Place for hash_keys */
  hash_get_key get_key;
  void (*free)(void *);
  CHARSET_INFO *charset;
} HASH;

_hash_init

HASHを初期化する。
CALLER_INFOを受け取るために、hash_initマクロ経由で実行される。

CHARSET_INFO

include/m_ctype.hで定義されている。

my_hash_insert

ハッシュテーブルにデータを登録する。
関数の前半部分は、リニアハッシュのBucketを拡張する処理。
後半部分(/* Check if we are at the empty position */以降)がデータ登録処理。

rec_hashnr

unsigned int rec_hashnr(HASH *hash,const byte *record)
{
  uint length;
  byte *key= (byte*) hash_key(hash,record,&length,0);
  return calc_hash(hash,key,length);
}

hash_keyでキーを取り出した後、calc_hashでハッシュ値を計算する

hash_key

static inline char*
hash_key(HASH *hash,const byte *record,uint *length,my_bool first)
{
  if (hash->get_key)
    return (*hash->get_key)(record,length,first);
  *length=hash->key_length;
  return (byte*) record+hash->key_offset;
}

ハッシュのキーとキーの長さを取り出す。
HASH->get_keyに関数ポインタが設定されているときは、その関数を使う。
たとえばtable_def_cacheでは、get_keyにtable_def_key関数が使われる。
get_keyが指定されていないときは、長さ(length)にHASH->key_lengthが設定され、キーにrecord + hash->key_offsetを返す。

calc_hash

static uint calc_hash(HASH *hash,const byte *key,uint length)
{
  ulong nr1=1, nr2=4;
  hash->charset->coll->hash_sort(hash->charset,(uchar*) key,length,&nr1,&nr2);
  return nr1;
}

HASH->charset->coll->hash_sortの関数を使って、ハッシュ値を計算する。
たとえばtable_def_cacheでは、hash_sortにmy_hash_sort_binが使用される。