Làm cách nào để Hashes hoạt động trong lập trình?

Question

Làm thế nào để băm hoạt động trong lập trình? Làm thế nào tôi nghĩ về một băm là một cái gì đó cho phép tôi khả năng sử dụng một số giá trị duy nhất để lấy một số dữ liệu. Giống như nếu chúng ta có một mảng và tôi bắt đầu đặt mọi thứ vào mảng, nếu tôi có một biến khác theo dõi mục nào nằm trong khe 0,1,2 ... thì tôi có khả năng tìm kiếm một mục ngay lập tức. Đó có phải là băm không?

Mục đích của băm là gì?

Khi nào băm nên được triển khai? Một hash tương tự như thế nào về cấu trúc dữ liệu?

Điều tôi nghĩ tôi biết về băm là nó cho phép chúng tôi có khả năng truy xuất mục trong O (1). Đúng không?

Answer 1

Bản đồ băm/từ điển là cấu trúc dữ liệu khóa/giá trị lưu trữ các đối tượng trong nhóm dựa trên giá trị của hàm băm. Các khóa này phải là duy nhất nhưng giá trị hàm băm (đôi khi được gọi là mã băm) không nhất thiết phải là duy nhất.

Giống như nếu chúng ta có mảng và tôi bắt đầu đặt htings trong mảng, nếu tôi có một biến thể khác theo dõi mục nào nằm trong vị trí 0,1,2 ... thì tôi có khả năng đó ngay lập tức để tìm một mục. Đó có phải là băm không?

No. Hàm băm là hàm xác định luôn mang cùng giá trị cho đối tượng. Mã băm không thay đổi tùy thuộc vào nơi đối tượng được lưu trữ.

Điều tôi nghĩ tôi biết về băm là nó cho phép chúng tôi có khả năng truy xuất mục trong O (1). Đúng không?

Gần đúng. Từ điển có O (1) độ phức tạp để tra cứu nếu không có quá nhiều xung đột mã băm. Tuy nhiên, nếu hàm băm kém và mọi đối tượng có giá trị băm giống nhau thì từ điển có thể có hiệu suất O (n) thay thế.

Answer 2

Hàm băm giống như tên của một người - đó là một cách ngắn để ghi nhớ một người, mặc dù nó không phải là duy nhất. Nếu bạn cần tìm một số thông tin về một người nào đó, bạn có thể chỉ họ bằng tên của họ và bạn chỉ cần thực hiện các kiểm tra khác nếu hai hoặc nhiều người có cùng tên.

Đó là sức mạnh của băm, và cũng giống như ghi nhớ mọi người dễ dàng hơn nhiều so với số an sinh xã hội, việc tìm kiếm một đối tượng bằng mã băm của nó dễ dàng hơn nhiều so với thực sự so sánh đối tượng với mọi thứ đã có trong bộ sưu tập của bạn. Bây giờ, trong ví dụ này, nếu bạn đang tìm kiếm ai đó trong danh bạ theo tên, bạn có thể tìm thấy chúng trong thời gian O (log n), bởi vì các tên được sắp xếp theo thứ tự abc, và bởi vì bạn cần thực hiện tìm kiếm nhị phân. Tuy nhiên, nếu bạn "băm" 100 người sinh vào những năm 1900 theo năm sinh của họ, thì bạn chỉ cần tối đa 4 so sánh trong danh bạ/thẻ (mỗi chữ số) để tìm bất kỳ một năm nào bằng băm, là thời gian không đổi. Sau đó, nếu hai người được sinh ra trong cùng bạn, bạn có thể sử dụng thông tin khác để tìm người bạn cần và trung bình nếu bảng của bạn không quá đầy đủ (giả sử, nếu bạn có tối đa 50 người trong 100 năm khác nhau sinh), tra cứu của bạn sẽ không đổi.

(Nếu bảng của bạn được nhiều hơn, nói rằng, 50% đầy đủ, bạn luôn có thể tăng gấp đôi kích thước của nó, để giữ cho số lượng va chạm thấp và do đó để giữ cho tra cứu của bạn nhanh chóng.)

---

Thông tin thêm :

Nếu bạn đã từng nghe đến MD5 hoặc SHA-1 băm SHA-2 cho tệp, chúng giống như "dấu vân tay" của tệp. Mặc dù có thể có hai tệp với cùng một giá trị băm, nhưng điều này được thực hiện rất khó xảy ra, vì mục đích thực tế, điều đó là không thể; do đó, nếu bạn có băm của hai tệp, bạn có thể so sánh các tệp theo dấu vân tay của chúng thay vì theo dữ liệu của chúng, nhanh hơn rất nhiều.

Answer 3

A hash giúp tra cứu nhanh hơn thay vì lặp qua mảng hoặc cây. Nó làm cho nó có thể tìm kiếm O(1) thời gian với ít sử dụng bộ nhớ.