Bảng băm VS mảng kết hợp

Question

Gần đây tôi đã đọc về bảng băm trong một cuốn sách rất nổi tiếng "Introduction to Algorithms". Tôi đã không sử dụng chúng trong bất kỳ ứng dụng thực tế nào được nêu ra, nhưng muốn. Nhưng tôi không biết bắt đầu như thế nào.
Bất cứ ai có thể cho tôi một số mẫu sử dụng nó, ví dụ, làm thế nào để nhận ra một ứng dụng từ điển (như ABBYY Lingvo) bằng cách sử dụng bảng băm?
Và cuối cùng tôi muốn biết sự khác biệt giữa các bảng băm và mảng kết hợp trong PHP, tôi có nghĩa là tôi nên sử dụng công nghệ nào và trong tình huống nào?
Nếu tôi sai (xin thứ lỗi) hãy sửa tôi, bởi vì thực sự tôi bắt đầu với bảng băm và tôi có kiến ​​thức cơ bản (lý thuyết) về chúng.
Cảm ơn rất nhiều.

Answer 1

Trong PHP, mảng kết hợp được triển khai dưới dạng thẻ bắt đầu bằng một chút chức năng bổ sung.

Tuy nhiên về mặt kỹ thuật, một mảng kết hợp không giống với một hashtable - nó chỉ đơn giản là thực hiện một phần với một hashtable đằng sau hậu trường. Bởi vì hầu hết việc thực hiện của nó là một hashtable, nó có thể làm mọi thứ một hashtable có thể - nhưng nó cũng có thể làm được nhiều hơn.

Ví dụ, bạn có thể lặp qua một mảng kết hợp bằng cách sử dụng vòng lặp for, mà bạn không thể thực hiện với một hashtable. Vì vậy, mặc dù chúng tương tự nhau, một mảng kết hợp thực sự có thể thực hiện một số superset của những gì một hashtable có thể làm - vì vậy chúng không chính xác giống nhau. Hãy nghĩ về nó như hashtables cộng thêm chức năng.

ví dụ Code:

Sử dụng một mảng kết hợp như một Hashtable:

$favoriteColor = array(); 
$favoriteColor['bob']='blue'; 
$favoriteColor['Peter']='red'; 
$favoriteColor['Sally']='pink'; 
echo 'bob likes: '.$favoriteColor['bob']."\n"; 
echo 'Sally likes: '.$favoriteColor['Sally']."\n"; 
//output: bob likes blue 
//  Sally likes pink 

Looping thông qua một mảng kết hợp:

$idTable=array(); 
$idTable['Tyler']=1; 
$idTable['Bill']=20; 
$idTable['Marc']=4; 
//up until here, we're using the array as a hashtable. 

//now we loop through the array - you can't do this with a hashtable: 
foreach($idTable as $person=>$id) 
    echo 'id: '.$id.' | person: '.$person."\n"; 

//output: id: 1 | person: Tyler 
//  id: 20 | person: Bill 
//  id: 4 | person: Marc 

Lưu ý đặc biệt như thế nào trong ví dụ thứ hai , thứ tự của từng phần tử được duy trì (Tyler, Bill Marc) dựa trên thứ tự mà chúng được nhập vào mảng. Đây là sự khác biệt chính giữa mảng kết hợp và hashtables. Một hashtable duy trì không có kết nối giữa các mục mà nó nắm giữ, trong khi một mảng kết hợp PHP (bạn thậm chí có thể sắp xếp một mảng kết hợp PHP).

Answer 2

mảng php Về cơ bản là các bảng băm

Answer 3

Mảng kết hợp là mảng mà bạn không truy cập các phần tử theo chỉ mục, mà bằng một khóa. Cách thức hoạt động bên trong này được thực hiện cụ thể (không có quy tắc làm thế nào nó phải hoạt động). Một mảng liên kết có thể được thực hiện bởi một bảng băm (hầu hết các triển khai sẽ làm điều đó), nhưng nó cũng có thể được thực hiện bởi một số cấu trúc cây hoặc danh sách bỏ qua hoặc thuật toán chỉ lặp qua tất cả các phần tử trong mảng và tìm khóa phù hợp (điều này sẽ rất chậm, nhưng nó hoạt động).

Bảng băm là cách lưu trữ dữ liệu trong đó giá trị được liên kết với khóa và nơi bạn dự định tìm giá trị cho các khóa trong khoảng thời gian cố định (thường là gần như). Điều này nghe chính xác như những gì bạn mong đợi của một mảng kết hợp, đó là lý do tại sao hầu hết các bảng băm thời gian được sử dụng để thực hiện các mảng đó, nhưng đó không phải là bắt buộc.

Answer 4

Sự khác biệt giữa mảng kết hợp và bảng băm là mảng kết hợp là loại dữ liệu, trong khi bảng băm là triển khai dữ liệu. Rõ ràng loại mảng kết hợp là rất quan trọng trong nhiều ngôn ngữ lập trình hiện tại: Perl, Python, PHP, vv Bảng băm là cách chính để triển khai mảng kết hợp, nhưng không phải là cách duy nhất. Và mảng kết hợp là việc sử dụng chính các bảng băm, nhưng không hoàn toàn là việc sử dụng duy nhất. Vì vậy, nó không phải là họ là như nhau, nhưng nếu bạn đã có mảng kết hợp, sau đó bạn thường không nên lo lắng về sự khác biệt.

Vì lý do hiệu suất, điều quan trọng là phải biết rằng các mảng kết hợp trong ngôn ngữ yêu thích của bạn được triển khai dưới dạng băm. Và nó có thể là quan trọng để có một số ý tưởng về chi phí trên không của việc thực hiện đó. Bảng băm chậm hơn và sử dụng nhiều bộ nhớ hơn mảng tuyến tính khi bạn thấy chúng trong C.

Perl gộp hai khái niệm lại với nhau bằng cách gọi mảng kết hợp "hashes". Giống như một số tính năng của Perl, nó không phải là khá sai, nhưng nó cẩu thả.

Answer 5

Một mảng trong PHP thực sự là bản đồ được sắp xếp, không phải là có thể bắt đầu. Sự khác biệt chính giữa bản đồ và hashtable bao gồm không có khả năng nhớ thứ tự trong các phần tử đã được thêm vào. Mặt khác, hashtables nhanh hơn nhiều so với bản đồ. Độ phức tạp của việc lấy một phần tử từ bản đồ là O (nlogn) và từ hashtable là O (1).