cat brain.log | less

Getting it down on `paper`

Fast Hash Function for Strings

Pre-condition: str is null terminated.

int hash(const void * str) {
  int val = 0;
  const char *ptr;
  int tmp;
 
  while (*ptr != '\0') {
    val = (val << 4) + (*ptr);
    if (tmp = (val & 0xf0000000)) {
      val = val ^ (tmp >> 24);
      val = val ^ tmp;
    }
  }
  ptr++;
  return val;
}

Or in PHP:

function hash($str) { 
  var $val = 0;
  for($i=0,$n=strlen($str); $i<$n; $i++) {
    $val = ($val<<4) + ord($str{$i});
    if( $tmp = ($val & 0xf0000000) ) { 
      $val = $val ^ ($tmp>>24);
      $val = $val ^ $tmp;
    }
  }
  return $val;
}

Now all you have to do is mod the returned value by the size of the hash table and you have the target address for the first pass of a hash table with double-hashing.

 

Comments

No comments so far.

(comments are closed)