Mở địa chỉ so với chuỗi riêng biệt

Question

Lược đồ xử lý va chạm hashmap nào tốt hơn khi hệ số tải gần 1 để đảm bảo lãng phí bộ nhớ tối thiểu?

Cá nhân tôi nghĩ rằng câu trả lời là mở giải quyết với thăm dò tuyến tính, bởi vì nó không cần bất kỳ không gian lưu trữ bổ sung trong trường hợp va chạm. Điều này có đúng không?

Answer 1

Trả lời câu hỏi: Lược đồ xử lý va chạm hashmap nào tốt hơn khi hệ số tải gần 1 đến đảm bảo lãng phí bộ nhớ tối thiểu?

Mở địa chỉ/thăm dò cho phép điền đầy đủ. Bởi vì như bạn đã nói như vậy chính mình, không có không gian thêm cần thiết cho va chạm (chỉ, tốt, có thể thời gian - tất nhiên điều này cũng giả định hàm băm không phải là hoàn hảo).

Nếu bạn không chỉ định "hệ số tải gần 1" hoặc chỉ số "chi phí" được bao gồm trong câu hỏi thì nó sẽ hoàn toàn khác.

Mã hóa vui vẻ.

Answer 2

Một bản băm đầy đủ sẽ làm suy giảm thành tìm kiếm tuyến tính, vì vậy bạn sẽ muốn giữ chúng dưới 90% đầy đủ.

Bạn thích hợp với việc mở địa chỉ bằng cách sử dụng ít bộ nhớ hơn, chuỗi sẽ cần một con trỏ hoặc trường bù trừ trong mỗi nút.

Tôi đã tạo cấu trúc dữ liệu chia sẻ khi tôi cần hashtables rất nhẹ sẽ không có nhiều phụ trang. Để giữ mức sử dụng bộ nhớ thấp, tất cả dữ liệu được nhúng vào cùng một khối bộ nhớ, với cấu trúc HashArray lúc bắt đầu, sau đó hai mảng cho các giá trị băm &. Hasharray chỉ có thể được sử dụng với khóa tra cứu được lưu trữ trong giá trị.

typedef uint16_t HashType; /* this can be 32bits if needed. */ 
typedef uint16_t HashSize; /* this can be made 32bits if large hasharrays are needed. */ 
struct HashArray { 
    HashSize length;  /* hasharray length. */ 
    HashSize count;   /* number of hash/values pairs contained in the hasharray. */ 
    uint16_t value_size; /* size of each value. (maximum size of value 64Kbytes) */ 
    /* these last two fields are just for show, they are not defined in the HashArray struct. */ 
    uint16_t hashs[length]; /* array of hashs for each value, this helps with resolving bucket collision */ 
    uint8_t values[length * value_size]; /* array holding all values. */ 
}; 
#define hasharray_get_hashs(array) (HashType *)(((uint8_t *)(array)) + sizeof(HashArray)) 
#define hasharray_get_values(array) ((uint8_t *)(array)) + sizeof(HashArray) + \ 
             ((array)->length * sizeof(HashType)) 
#define hasharray_get_value(array, idx) (hasharray_get_values(array) + ((idx) * (array)->value_size)) 

Các macro hasharray_get_hashs & hasharray_get_values ​​được sử dụng để có được & mảng 'giá trị' the 'hashs'.

Tôi đã sử dụng điều này để thêm tra cứu nhanh các đối tượng phức tạp đã được lưu trữ trong một mảng. Các đối tượng có một trường 'tên' chuỗi được sử dụng để tra cứu. Các tên được băm và chèn vào phần hasharray với các chỉ mục đối tượng. Các giá trị được lưu trữ trong hasharray có thể là chỉ mục/con trỏ/toàn bộ đối tượng (tôi chỉ sử dụng các giá trị chỉ mục 16 bit nhỏ).

Nếu bạn muốn đóng gói bộ sưu tập cho đến khi nó gần đầy, thì bạn sẽ muốn sử dụng Hashs 32 bit đầy đủ thay vì các mã băm 16 bit được định nghĩa ở trên. Băm 32 bit lớn hơn sẽ giúp giữ cho tìm kiếm nhanh chóng khi phần còn lại chiếm hơn 90%.

Phần chia nhỏ như được định nghĩa ở trên chỉ có thể chứa tối đa 65535, điều này là tốt vì tôi không bao giờ sử dụng nó trên bất kỳ thứ gì có giá trị vài trăm. Bất cứ điều gì cần nhiều hơn mà chỉ nên sử dụng một hashtable bình thường. Nhưng nếu bộ nhớ thực sự là một vấn đề, loại HashSize có thể được thay đổi thành 32 bit. Ngoài ra, tôi sử dụng độ dài power-of-2 để giữ cho tra cứu băm nhanh chóng. Một số người thích sử dụng độ dài xô chính, nhưng điều đó chỉ cần thiết nếu hàm băm có phân phối kém.

#define hasharray_empty_hash 0xFFFF /* hash value to mark empty slots. */ 
void *hasharray_search(HashArray *array, HashType hash, uint32_t *next) { 
    HashType *hashs = hasharray_get_hashs(array); 
    uint32_t mask = array->length - 1; 
    uint32_t start_idx; 
    uint32_t idx; 

    hash = (hash == hasharray_empty_hash) ? 0 : hash; /* need one hash value to mark empty slots. */ 
    start_hash_idx = (hash & mask); 
    if(*next == 0) { 
    idx = start_idx; /* new search. */ 
    } else { 
    idx = *next & mask; /* continuing search to next slot. */ 
    } 

    /* find hash in hash array. */ 
    do { 
    /* check for hash match. */ 
    if(hashs[idx] == hash) goto found_hash; 
    /* check for end of chain. */ 
    if(hashs[idx] == hasharray_empty_hash) break; 
    idx++; 
    idx &= mask; 
    } while(idx != start_idx); 
    /* maximum tries reached (i.e. did a linear search of whole array) or end of chain. */ 
    return NULL; 

found_hash: 
    *next = idx + 1; /* where to continue search at, if this is not the right value. */ 
    return hasharray_get_values(array) + (idx * array->value_size); 
} 

va chạm băm sẽ xảy ra để mã tìm kiếm hasharray_search() cần so sánh khóa tìm kiếm với khóa được lưu trữ trong đối tượng giá trị. Nếu chúng không khớp thì hasharray_search() được gọi lại. Ngoài ra các khóa không phải duy nhất có thể tồn tại, vì việc tìm kiếm có thể tiếp tục cho đến khi 'NULL' được trả lại để tìm tất cả các giá trị khớp với một khóa. Chức năng tìm kiếm sử dụng thăm dò tuyến tính để được cache freindly.

typedef struct { 
    char *name; /* this is the lookup key. */ 
    char *type; 
    /* other field info... */ 
} Field; 

typedef struct { 
    Field *list;   /* array of Field objects. */ 
    HashArray *lookup; /* hasharray for fast lookup of Field objects by name. The values stored in this hasharray are 16bit indices. */ 
    uint32_t field_count; /* number of Field objects in 'list'. */ 
} Fields; 

extern Fields *fields_new(uint16_t count) { 
    Fields *fields; 
    fields = calloc(1, sizeof(Fields)); 
    fields->list = calloc(count, sizeof(Field)); 
    /* allocate hasharray to hold at most 'count' uint16_t values. 
    * The hasharray will round 'count' up to the next power-of-2. 
    * That power-of-2 length must be atleast (count+1), so that there will always be one empty slot. 
    */ 
    fields->lookup = hasharray_new(count, sizeof(uint16_t)); 
    fields->field_count = count; 
} 

extern Field *fields_lookup_by_name(Fields *fields, const char *name) { 
    HashType hash = str_to_hash(name); 
    Field *field; 
    uint32_t next = 0; 
    uint16_t *rc; 
    uint16_t idx; 

    do { 
    rc = hasharray_search(fields->lookup, hash, &next); 
    if(rc == NULL) break; /* field not found. */ 
    /* found a possible match. */ 
    idx = *rc; 
    assert(idx < fields->field_count); 
    field = &(fields->list[idx]); 
    /* compare lookup name with field's name. */ 
    if(strcmp(name, field->name) == 0) { 
     /* found match. */ 
     return field; 
    } 
    /* field didn't match continue search to next field. */ 
    } while(1); 
    return NULL; 
} 

Tìm kiếm trường hợp xấu nhất sẽ làm giảm tìm kiếm tuyến tính của toàn bộ mảng nếu nó đầy 99% và khóa không tồn tại. Nếu các khóa là số nguyên, thì tìm kiếm tuyến tính không được để xấu, cũng chỉ có các khóa có cùng giá trị băm sẽ cần phải được so sánh. Tôi cố gắng giữ kích thước băm nhỏ để chúng chỉ chiếm khoảng 70-80%, không gian lãng phí trên các khe trống không nhiều nếu các giá trị chỉ có giá trị 16 bit. Với thiết kế này, bạn chỉ lãng phí 4byte mỗi khe trống khi sử dụng giá trị băm 16 bit & Giá trị chỉ mục 16 bit. Mảng các đối tượng (Các cấu trúc trường trong ví dụ trên) không có các điểm trống.

Ngoài ra, hầu hết các triển khai có thể bắt đầu mà tôi đã thấy không lưu trữ các băm được tính toán và yêu cầu so sánh khóa đầy đủ để giải quyết xung đột nhóm. So sánh các hash giúp rất nhiều vì chỉ một phần nhỏ giá trị băm được sử dụng để tra cứu nhóm.

Answer 3

Như những người khác đã nói, trong thăm dò tuyến tính, khi hệ số tải gần 1, độ phức tạp thời gian gần tìm kiếm tuyến tính. (Khi nó đầy, vô hạn của nó.) Có một giao dịch hiệu quả về bộ nhớ ở đây. Trong khi tách riêng chuỗi luôn cho chúng ta thời gian liên tục về lý thuyết.

Thông thường, theo thăm dò tuyến tính, bạn nên giữ hệ số tải giữa 1/8 và 1/2. khi mảng là 1/2 đầy đủ, chúng tôi thay đổi kích thước nó để tăng gấp đôi kích thước của mảng ban đầu. (Tham khảo: Thuật toán của Robert Sedgewick. Kevin Wayne.). Khi xóa, chúng tôi thay đổi kích cỡ mảng thành 1/2 kích thước ban đầu. Nếu bạn thực sự quan tâm, nó là tốt cho bạn để bắt đầu với cuốn sách tôi đã đề cập ở trên. Trong thực tế, nó nói rằng 0,72 là một giá trị thực nghiệm chúng ta thường sử dụng.