Tạo Bảng băm với hai mảng

Question

Có ai biết cách làm điều này và mã giả sẽ trông như thế nào không?

Như chúng ta đều biết bảng băm lưu trữ các cặp khóa, giá trị và khi một khóa được gọi, hàm sẽ trả về giá trị được liên kết với khóa đó. Điều tôi muốn làm là hiểu cấu trúc cơ bản trong việc tạo ra chức năng ánh xạ đó. Ví dụ, nếu chúng ta sống trong một thế giới mà không có các hàm được định nghĩa trước đó trừ các mảng, làm sao chúng ta có thể tái tạo các Hashmaps mà chúng ta có ngày hôm nay?

Answer 1

Trên thực tế, một số ngày nay HashMap implentations đang thực sự làm bằng mảng như bạn đề xuất. Hãy để tôi phác họa cách hoạt động:

Hàm băm Hàm băm biến khóa thành chỉ mục cho mảng đầu tiên (mảng K). Một hàm băm như MD5 hoặc đơn giản hơn, thường bao gồm một toán tử modulo, có thể được sử dụng cho điều này.

Xô Việc triển khai Hashmap dựa trên mảng đơn giản có thể sử dụng nhóm để đối phó với việc thu thập. Mỗi phần tử ('bucket') trong mảng K chứa chính nó một mảng (mảng P) của các cặp. Khi thêm hoặc truy vấn một phần tử, hàm băm sẽ đưa bạn đến đúng nhóm trong K, chứa mảng mong muốn của bạn P. Bạn sau đó lặp qua các phần tử trong P cho đến khi bạn tìm thấy một khóa khớp hoặc bạn gán một phần tử mới tại cuối P.

phím Mapping để xô sử dụng Hash Bạn nên chắc chắn rằng số lượng thùng (tức là kích thước của K) là một sức mạnh của 2, giả sử 2^b. Để tìm chỉ mục nhóm chính xác cho một số khóa, hãy tính toán Hash (khóa) nhưng chỉ giữ lại các bit b đầu tiên. Đây là chỉ mục của bạn khi truyền tới một số nguyên.

Thay đổi tỷ lệ Tính toán băm của khóa và tìm đúng nhóm rất nhanh. Nhưng một khi một xô trở nên đầy đủ hơn, bạn sẽ phải lặp lại nhiều hơn và nhiều hơn nữa các mặt hàng trước khi bạn nhận được một bên phải. Vì vậy, điều quan trọng là phải có đủ nhóm để phân phối đúng đối tượng hoặc Hashmap của bạn sẽ trở nên chậm.

Bởi vì bạn thường không biết bạn muốn lưu trữ bao nhiêu đối tượng trong Hashmap trước, bạn nên tự động tăng hoặc thu nhỏ bản đồ. Bạn có thể giữ một số lượng các đối tượng được lưu trữ, và một khi nó đi qua một ngưỡng nhất định bạn tạo lại toàn bộ cấu trúc, nhưng lần này với một kích thước lớn hơn hoặc nhỏ hơn cho mảng K.Bằng cách này, một số thùng trong K đã rất đầy đủ bây giờ sẽ có các yếu tố của chúng được chia cho một số nhóm, do đó hiệu suất sẽ tốt hơn.

Lựa chọn thay thế Bạn cũng có thể sử dụng mảng hai chiều thay vì mảng mảng hoặc bạn có thể trao đổi mảng P cho danh sách được liên kết. Hơn nữa, thay vì giữ tổng số đối tượng đã lưu trữ, bạn có thể chỉ cần chọn tạo lại (tức là rescale) hashmap khi một trong các thùng chứa nhiều hơn một số mục được cấu hình.

Biến thể của những gì bạn đang yêu cầu được mô tả là 'bảng băm mảng' trong Hash table Wikipedia entry.

Mã Đối với mẫu mã, hãy xem here.

Hy vọng điều này sẽ hữu ích.

Answer 2

Bạn có thể chính xác hơn không? Một mảng có chứa khóa hay không, giá trị kia có phải là giá trị không?

Nếu vậy, đây là một ví dụ trong Java (nhưng có vài đặc thù của ngôn ngữ này ở đây):

for (int i = 0; i < keysArray.length; i++) { 
    map.put(keysArray[i], valuesArray[i]); 
} 

Tất nhiên, bạn sẽ phải nhanh chóng đối tượng map của bạn (nếu bạn đang sử dụng Java, Tôi khuyên bạn nên sử dụng HashMap<Object, Object> thay vì HashTable lỗi thời) và cũng kiểm tra các mảng của mình để tránh các đối tượng null và kiểm tra xem chúng có cùng kích thước hay không.

Answer 3

Ý bạn là như thế này?

Sau đây là sử dụng Ruby irb như một ví dụ:

cities = ["LA", "SF", "NY"] 
=> ["LA", "SF", "NY"] 

items = ["Big Mac", "Hot Fudge Sundae"] 
=> ["Big Mac", "Hot Fudge Sundae"] 

price = {} 
=> {} 

price[[cities[0], items[1]]] = 1.29 
=> 1.29 

price 
=> {["LA", "Hot Fudge Sundae"]=>1.29} 

price[[cities[0], items[0]]] = 2.49 
=> 2.49 

price[[cities[1], items[0]]] = 2.99 
=> 2.99 

price 
=> {["LA", "Hot Fudge Sundae"]=>1.29, ["LA", "Big Mac"]=>2.49, ["SF", "Big Mac"]=>2.99} 

price[["LA", "Big Mac"]] 
=> 2.49 

Answer 4

Sample Giải thích:

Tại nguồn dưới đây, về cơ bản nó không có hai điều:

1. Bản đồ Đại diện

• Một số (X số trong danh sách) của danh sách
• X là 2 số lượng N danh sách là xấu. A (2 công suất N) -1 hoặc (2 công suất N) +1 hoặc số nguyên tố là tốt.

Ví dụ:

List myhashmap [hash_table_size]; 
// an array of (short) lists 
// if its long lists, then there are more collisions 

LƯU Ý: đây là mảng của mảng, không phải là hai mảng (Tôi không thể nhìn thấy một hashmap generic có thể, trong một cách tốt chỉ với 2 mảng)

Nếu bạn biết Thuật toán> Lý thuyết đồ thị> Danh sách adjacency, này trông giống giống hệt nhau.

2.hàm băm

Và hàm băm chuyển xâu (đầu vào) cho một số (giá trị băm), đó là chỉ số của mảng

• khởi tạo giá trị băm để char đầu tiên (sau khi chuyển đổi sang int)
• cho mỗi char hơn nữa, trái thay đổi 4 bit, sau đó thêm char (sau khi chuyển đổi sang int)

Ví dụ,

int hash = input[0]; 
for (int i=1; i<input.length(); i++) { 
    hash = (hash << 4) + input[i] 
} 

hash = hash % list.size() 
// list.size() here represents 1st dimension of (list of lists) 
//  that is 1st dimension size of our map representation from point #1 
//  which is hash_table_size 

Xem tại liên kết đầu tiên:

int HTable::hash (char const * str) const 

Nguồn:
http://www.relisoft.com/book/lang/pointer/8hash.html
How does a hash table work?

Cập nhật
Đây là nguồn gốc xuất sắc nhất: http://algs4.cs.princeton.edu/34hash/