如何制作一个灵活大小的哈希表

Question

我想使用这段筛选大文件的代码。目前，我在硬编码哈希表的大小，假设输入有5000万行。我希望总行数占哈希表大小的37%。目前实现方式是将0x8000000的37%大约设置为5000万。但是，在实际操作中，我不知道开始处理之前输入的大小。我该如何修改代码以自动调整哈希表大小，使其正确？同时，速度也很重要，因为筛选的目的是为了节省时间。

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>

// Should be 37% occupied with 50m entries
#define TABLE_SIZE 0x8000000
#define MASK (TABLE_SIZE - 1)
#define BUFFER_SIZE 16384
#define END_OF_FILE (-1)
#define DEFAULT_VALUE (-1)

typedef struct Row {
  int32_t a;
  int32_t b;
  int32_t t;
} Row;

int32_t hash(int32_t a) {
  return a * 428916315;
}

void insert(Row * table, Row row) {
  long loc = hash(row.a) & MASK; // Entries are hashed on a
  long inc = 0;
  while (inc <= TABLE_SIZE) {
    loc = (loc + inc) & MASK;
    inc++;
    if (table[loc].a == DEFAULT_VALUE) {
      table[loc] = row;
      break;
    }
  }
}

int readChar(FILE * input, char * buffer, int * pos, int * limit) {
  if (*limit < *pos) {
    return buffer[(*limit)++];
  } else {
    *limit = 0;
    *pos = fread(buffer, sizeof(char), BUFFER_SIZE, input);
    if (*limit < *pos) {
      return buffer[(*limit)++];
    } else return END_OF_FILE;
  }
}

void readAll(char * fileName, Row * table) {
  char* buffer = (char*) malloc(sizeof(char) * BUFFER_SIZE);
  int limit = 0;
  int pos = 0;

  FILE * input = fopen(fileName, "rb");

  int lastRead;
  Row currentRow;
  uint32_t * currentElement = &(currentRow.a);

  // As with the Scala version, we read rows with an FSM. We can
  // roll up some of the code using the `currentElement` pointer
  while (1) {
    switch(lastRead = readChar(input, buffer, &pos, &limit)) {
      case END_OF_FILE:
        fclose(input);
        return;
      case ' ':
        if (currentElement == &(currentRow.a)) currentElement = &(currentRow.b);
        else currentElement = &(currentRow.t);
        break;
      case '\n':
        insert(table, currentRow);
        currentRow.a = 0;
        currentRow.b = 0;
        currentRow.t = 0;
        currentElement = &(currentRow.a);
        break;
      default:
        *currentElement = *currentElement * 10 + (lastRead - '0');
        break;
    }
  }
  //printf("Read %d", lastRead);
}

int main() {
  Row* table = (Row*) malloc(sizeof(Row) * TABLE_SIZE);
  memset(table, 255, sizeof(Row) * TABLE_SIZE);

  readAll("test.file", table);

  // We'll iterate through our hash table inline - passing a callback
  // is trickier in C than in Scala, so we just don't bother
  for (size_t i = 0; i < TABLE_SIZE; i++) {
    Row * this = table + i;
    if (this->a != DEFAULT_VALUE) {
      // Lookup entries `that`, where `that.a == this.b`
      long loc = hash(this->b) & MASK;
      long inc = 0;
      while (inc <= TABLE_SIZE) {
        loc = (loc + inc) & MASK;
        inc++;
        Row * that = table + loc;
        if ((this->b == that->a) && (0 <= that->t - this->t) && (that->t - this->t < 100)) {
          // Conditions are symmetric, so we output both rows
          printf("%d %d %d\n", this->a, this->b, this->t);
          printf("%d %d %d\n", that->a, that->b, that->t);
        }
        else if (that->b == DEFAULT_VALUE) break;
      }
    }
  }

  free(table);
  return 0;
}

- Simd

---

你需要重新组织或扩展哈希表，例如使用更大的桶，定期或在达到某个密度阈值时进行。实际上，这种重新组织几乎就像制作一个新的哈希表，并从旧表中填充条目一样。你可能需要类似于 newsize = 5*oldsize/4+10; 的东西。 - Basile Starynkevitch

你没有处理哈希冲突。你可以将表中的每个条目都变成一个 Row 的链表。 - ericbn

@ericbn 这是（或者至少是被设计成）开放式哈希。这应该避免了你提到的问题。https://zh.wikipedia.org/wiki/%E5%BC%80%E5%9C%A3%E5%9E%8B%E5%93%88%E5%B8%8C - Simd

@user2179021，将冲突视为同一桶中的列表可以使您保持表大小固定，并让项目在另一个维度中增长。 - ericbn

类似于stackoverflow.com/questions/16907423/converting-static-to-dynamic-hash-table/16908837 - chux - Reinstate Monica

Answer 1

读取文件的前100 KB，计算其中的换行符数量。根据此来推断整个文件中可能遇到的总换行符数量（使用总大小为 O(1)）。如果输入文件相对规则，这将给出一个足以用于调整哈希表大小的接近猜测。

- John Zwinck