如何製作靈活大小的哈希表

我想使用這個代碼來過濾大文件。目前我很難編碼散列表的大小，假設輸入有五千萬行。我希望行的總數是散列表大小的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; 
}

來源

2014-09-05 eleanora

您必須重新組織或擴大您的哈希表，例如不時或者當你達到一定的密度閾值時更大的桶。在實踐中，重組幾乎就像製作一個新的哈希表並填入舊錶中的條目。你可能會想要像'newsize = 5 * oldsize/4 + 10;' – 2014-09-05 12:50:08

你不是在處理散列衝突。你可以讓表格中的每個條目成爲「行」的鏈接列表。 – ericbn 2014-09-05 12:55:31

@ericbn它是（或至少是它的意思）開放哈希。這應該避免你提到的問題。 https://en.wikipedia.org/wiki/Open_addressing – eleanora 2014-09-05 12:58:12

讀取文件的第一個，比方說100 KB，計算其換行符。從中推斷出猜測整個文件中可能遇到的換行符的總數（使用總大小爲O（1））。如果輸入文件相當規則，那麼這將給你一個足夠接近的猜測，以便確定散列表的大小。

來源

2014-09-05 12:59:16

如何製作靈活大小的哈希表

回答

相關問題