[MUSIC CHƠI] DOUG LLOYD: Bởi bây giờ bạn biết rất nhiều về mảng, và bạn biết rất nhiều về danh sách liên kết. Và chúng tôi đã thảo luận về các ưu và nhược điểm, chúng tôi đã thảo luận rằng danh sách liên kết có thể có được lớn hơn và nhỏ hơn, nhưng chúng chiếm kích thước hơn. Mảng là đơn giản hơn nhiều để sử dụng, nhưng chúng hạn chế trong nhiều như chúng ta phải thiết lập kích thước của các mảng ở đầu và sau đó chúng tôi đang mắc kẹt với nó. 

Nhưng đó là, chúng tôi đã khá hơn nhiều hết tất cả các chủ đề của chúng tôi về danh sách và các mảng liên kết. Hoặc có chúng tôi? Có lẽ chúng ta có thể làm điều gì đó thậm chí sáng tạo hơn. Và đó là loại cho vay ý tưởng của một bảng băm. 

Vì vậy, trong một bảng băm chúng ta sẽ cố gắng kết hợp một mảng với một danh sách liên kết. Chúng tôi sẽ có những lợi thế của mảng, như truy cập ngẫu nhiên, việc có thể chỉ cần đi vào mảng 4 yếu tố hoặc mảng phần 8 mà không cần phải lặp qua. Đó là khá nhanh, phải không? 

Nhưng chúng tôi cũng muốn có dữ liệu của chúng tôi cấu trúc có thể phát triển và thu nhỏ. Chúng tôi không cần, chúng tôi không muốn bị hạn chế. Và chúng tôi muốn có thể thêm và loại bỏ những thứ rất dễ dàng, mà nếu bạn gọi lại, là rất phức tạp với một mảng. Và chúng ta có thể gọi đây điều mới một bảng băm. 

Và nếu được thực hiện một cách chính xác, chúng ta đang loại dùng những ưu điểm của cả hai dữ liệu cấu trúc mà bạn đã nhìn thấy, mảng và danh sách liên kết. Chèn có thể bắt đầu có xu hướng về theta của 1. Theta, chúng tôi đã không thực sự thảo luận, nhưng theta chỉ là trường hợp trung bình, những gì đang thực sự xảy ra. Bạn không phải lúc nào có trường hợp xấu nhất, và bạn không phải lúc nào cũng sẽ có các trường hợp tốt nhất, vì vậy những gì kịch bản trung bình? 

Vâng một chèn trung bình vào một bảng băm có thể bắt đầu để có được gần với thời gian liên tục. Và xóa có thể nhận được gần với thời gian liên tục. Và tra cứu có thể nhận được gần với thời gian liên tục. That's-- chúng ta không có một dữ liệu cấu trúc nào đó có thể làm điều đó, và vì vậy điều này đã âm thanh như là một điều khá tuyệt vời. Chúng tôi đã thực sự giảm thiểu các nhược điểm của mỗi ngày của riêng mình. 

Để có được hiệu suất này nâng cấp, mặc dù chúng tôi cần phải suy nghĩ lại cách chúng ta thêm dữ liệu vào cấu trúc. Cụ thể chúng tôi muốn dữ liệu riêng của mình cho chúng tôi nơi cần đi trong cấu trúc. Và nếu chúng ta thì cần phải xem nếu nó trong cấu trúc, nếu chúng ta cần phải tìm thấy nó, chúng tôi muốn xem xét dữ liệu một lần nữa và có thể có hiệu quả, bằng cách sử dụng dữ liệu, truy cập ngẫu nhiên cho nó. Chỉ cần nhìn vào các dữ liệu chúng ta cần phải có một ý tưởng về nơi chính xác chúng tôi sẽ tìm thấy nó trong bảng băm. 

Bây giờ các nhược điểm của hàm băm bảng là họ đang thực sự khá xấu tại đặt hàng hoặc phân loại dữ liệu. Và trên thực tế, nếu bạn bắt đầu sử dụng chúng để đặt hàng hoặc loại dữ liệu bạn mất tất cả các lợi thế trước đây bạn đã về chèn và xóa. Hiện trở nên gần gũi hơn với theta của n, và chúng tôi đã cơ bản thụt lùi vào một danh sách liên kết. Và vì vậy chúng tôi chỉ muốn sử dụng băm bảng nếu chúng ta không quan tâm đến cho dù dữ liệu được sắp xếp. Đối với các bối cảnh trong đó bạn sẽ sử dụng chúng trong CS50 có thể bạn không quan tâm rằng các dữ liệu được sắp xếp. 

Vì vậy, một bảng băm là một sự kết hợp của hai phần riêng biệt mà chúng ta đã quen thuộc. Đầu tiên là một chức năng, trong đó chúng ta thường gọi một hàm băm. Và đó hàm băm sẽ trả lại một số nguyên không âm, mà chúng ta thường gọi một hashcode, OK? Cái thứ hai là một mảng, mà là khả năng lưu trữ dữ liệu của các loại chúng tôi muốn đặt vào cấu trúc dữ liệu. Chúng tôi sẽ tổ chức off trên liên kết yếu tố danh sách cho doanh nghiệp và chỉ bắt đầu với những điều cơ bản của một băm bảng để có được đầu của bạn xung quanh nó, và sau đó chúng tôi sẽ có thể thổi tâm trí của bạn một chút khi chúng ta kết hợp các mảng và danh sách liên kết với nhau. 

Ý tưởng cơ bản mặc dù là chúng ta mất một số dữ liệu. Chúng tôi chạy mà dữ liệu thông qua hàm băm. Và do đó, các dữ liệu được xử lý và nó phun ra một số, OK? Và sau đó với con số đó chúng ta chỉ cần lưu trữ các dữ liệu chúng tôi muốn lưu trữ trong các mảng ở vị trí đó. Vì thế chúng ta có thể bảng băm này của chuỗi. Nó có 10 yếu tố trong nó, vì vậy chúng ta có thể phù hợp với 10 chuỗi trong nó. 

Hãy nói rằng chúng tôi muốn băm John. Vì vậy, John là dữ liệu chúng tôi muốn chèn vào bảng băm này ở đâu đó. Nơi nào chúng ta đặt nó? Vâng điển hình với một mảng cho đến nay chúng ta có thể sẽ đặt nó trong mảng vị trí 0. Nhưng bây giờ chúng ta có hàm băm mới này. 

Và chúng ta hãy nói rằng chúng tôi chạy John thông qua hàm băm này và nó phun ra 4. Vâng đó là nơi chúng tôi sẽ muốn đưa John. Chúng tôi muốn đưa John trong mảng vị trí 4, bởi vì nếu chúng ta băm John again-- hãy nói rằng sau này chúng tôi muốn tìm kiếm và xem nếu John tồn tại trong hash này table-- tất cả chúng ta cần phải làm là chạy nó thông qua các hash cùng chức năng, có được số 4, và có thể tìm thấy John ngay trong cấu trúc dữ liệu của chúng tôi. Đó là khá tốt. 

Hãy nói rằng bây giờ chúng ta làm điều này một lần nữa, chúng tôi muốn băm Paul. Chúng tôi muốn thêm Paul vào bảng băm này. Hãy nói rằng lần này chúng tôi chạy Paul qua hàm băm, hashcode được tạo ra là 6. Vâng bây giờ chúng ta có thể đưa Paul tại vị trí mảng 6. Và nếu chúng ta cần phải nhìn lên xem Paul là trong bảng băm này, tất cả chúng ta cần phải làm là chạy Paul thông qua các hàm băm một lần nữa và chúng ta sẽ nhận được 6 ra một lần nữa. 

Và sau đó chúng ta chỉ cần nhìn tại vị trí mảng 6. Paul là có? Nếu vậy, anh ấy trong bảng băm. Paul là không có? Ông ấy không phải trong bảng băm. Nó khá dễ hiểu. 

Bây giờ làm thế nào để bạn xác định một hàm băm? Cũng có thực sự không có giới hạn số hàm băm có thể. Trong thực tế có một số thực sự, những người thực sự tốt trên internet. Có một số thực sự, những người thực sự xấu trên internet. Nó cũng khá dễ dàng để viết một xấu. 

Vì vậy, những gì làm nên một tốt hàm băm, phải không? Vâng một hàm băm tốt nên chỉ sử dụng các dữ liệu đang được băm, và tất cả các dữ liệu đang được băm. Vì vậy, chúng tôi không muốn sử dụng anything-- chúng ta không kết hợp bất cứ điều gì khác ngoài các dữ liệu. Và chúng tôi muốn sử dụng tất cả các dữ liệu. Chúng tôi không muốn chỉ cần sử dụng một mảnh của nó, chúng tôi muốn sử dụng tất cả của nó. Một hàm băm nên cũng được xác định. Điều đó có nghĩa là gì? Cũng có nghĩa là mỗi lần chúng tôi vượt qua các mảnh cùng chính xác của dữ liệu vào hàm băm chúng tôi luôn có được hashcode cùng ra. Nếu tôi vượt qua John vào hàm băm tôi nhận ra 4. Tôi sẽ có thể làm điều đó 10.000 lần và tôi sẽ luôn luôn nhận được 4. Vì vậy, không có con số ngẫu nhiên hiệu quả có thể được tham gia vào băm của chúng tôi tables-- trong hàm băm của chúng tôi. 

Một hàm băm cũng nên thống nhất phân phối dữ liệu. Nếu mỗi khi bạn chạy các dữ liệu thông qua các hàm băm bạn nhận được hashcode 0, đó có lẽ không tuyệt vời như vậy, phải không? Bạn có thể muốn lớn một loạt các mã băm. Cũng có những thứ có thể lây lan ra khắp bàn. Và cũng có thể nó sẽ là tuyệt vời nếu thực sự dữ liệu tương tự, như John và Jonathan, có thể được trải ra để cân nhắc địa điểm khác nhau trong bảng băm. Đó sẽ là một lợi thế tốt đẹp. 

Dưới đây là một ví dụ về một hàm băm. Tôi đã viết này lên trước đó. Nó không phải là một đặc biệt hàm băm tốt vì những lý do không thực sự chịu đi vào ngay bây giờ. Nhưng bạn có thấy những gì đang xảy ra ở đây? Nó có vẻ như chúng ta đang khai báo một biến gọi là tiền và thiết lập nó bằng 0. Và sau đó dường như tôi đang làm một cái gì đó miễn là strstr [j] là không bằng nhau để dấu gạch chéo ngược 0. Tôi đang làm gì ở đó? 

Điều này về cơ bản là giống nhau cách thực hiện [? strl?] và phát hiện khi bạn đã đạt đến kết thúc của chuỗi. Vì vậy, tôi không cần phải thực sự tính toán chiều dài của chuỗi, Tôi chỉ sử dụng khi tôi nhấn backslash 0 nhân vật tôi biết Tôi đã đạt đến kết thúc của chuỗi. Và sau đó tôi sẽ giữ lặp lại thông qua chuỗi, thêm strstr [j] để tổng hợp, và sau đó tại cuối ngày sẽ trở về sum mod HASH_MAX. 

Về cơ bản tất cả các hash này chức năng đang làm là thêm lên tất cả các giá trị ASCII của chuỗi của tôi, và sau đó nó trả lại một số hashcode modded của HASH_MAX. Đó có lẽ là kích thước các mảng của tôi, phải không? Tôi không muốn nhận được băm mã nếu mảng của tôi có kích thước 10, Tôi không muốn là nhận được ra mã băm 11, 12, 13 tuổi, tôi không thể đặt mọi thứ vào những vị trí của mảng, đó sẽ là bất hợp pháp. Tôi bị một lỗi phân khúc. 

Bây giờ đây là một cách nhanh chóng sang một bên. Nói chung bạn có thể sẽ không muốn viết hàm băm của riêng bạn. Nó thực sự là một chút một nghệ thuật, không phải là một khoa học. Và có rất nhiều mà đi vào chúng. Internet, như tôi đã nói, có đầy đủ của hàm băm thực sự tốt, và bạn nên sử dụng internet để tìm các hàm băm vì nó thực sự chỉ cần loại một không cần thiết lãng phí thời gian để tạo của riêng bạn. 

Bạn có thể viết cái đơn giản cho mục đích thử nghiệm. Nhưng khi bạn thực sự sẽ bắt đầu băm dữ liệu và lưu trữ nó vào một bảng băm bạn có lẽ sẽ muốn sử dụng một số chức năng đã được tạo ra cho bạn, mà tồn tại trên internet. Nếu bạn chỉ cần nhớ để trích dẫn nguồn của bạn. Không có lý do để ăn cắp bất cứ thứ gì ở đây. 

Cộng đồng khoa học máy tính là chắc chắn ngày càng tăng, và thực sự giá trị mã nguồn mở, và nó thực sự quan trọng để trích dẫn nguồn của bạn để mọi người có thể được ghi công cho công việc mà họ đang làm cho lợi ích của cộng đồng. Vì vậy, luôn luôn có sure-- và không chỉ cho hash chức năng, nhưng nói chung khi bạn sử dụng mã từ một nguồn bên ngoài, luôn luôn trích dẫn nguồn của bạn. Cung cấp tín dụng cho người đã làm một số công việc, do đó bạn không phải. 

OK như vậy chúng ta hãy xem lại này bảng băm cho một thứ hai. Đây là nơi chúng tôi rời off sau khi chúng ta chèn John và Paul vào bảng băm này. Bạn có thấy một vấn đề ở đây? Bạn có thể thấy hai. Nhưng đặc biệt, làm bạn xem lại vấn đề này? 

Nếu tôi băm gì Ringo, và nó Hóa ra sau khi chế biến rằng dữ liệu thông qua các hàm băm Ringo cũng tạo ra hashcode 6. Tôi đã nhận được dữ liệu ở hashcode-- mảng vị trí 6. Vì vậy, nó có thể có được một chút của một vấn đề đối với tôi bây giờ, phải không? 

Chúng tôi gọi đây là một vụ va chạm. Và các vụ va chạm xảy ra khi hai mẩu dữ liệu chạy qua cùng bảng băm chức năng mang lại hashcode cùng. Có lẽ chúng ta vẫn muốn có được cả mẩu dữ liệu vào bảng băm, nếu không chúng tôi sẽ không được chạy Ringo tự ý thông qua các hàm băm. Chúng ta có lẽ muốn có được Ringo vào mảng đó. 

Làm thế nào để chúng tôi làm điều đó, mặc dù nếu ông và Paul cả năng suất hashcode 6? Chúng tôi không muốn ghi đè Paul, chúng tôi muốn Paul có mặt ở đó quá. Vì vậy, chúng ta cần phải tìm một cách để có được các yếu tố vào bảng băm vẫn còn lưu giữ nhanh của chúng tôi chèn và nhanh chóng nhìn lên. Và một cách để đối phó với nó là để làm một cái gì đó gọi là tuyến tính thăm dò. 

Sử dụng phương pháp này nếu chúng ta có một va chạm, tốt, chúng ta làm gì? Vâng, chúng tôi không thể đưa anh ta trong mảng vị trí 6, hoặc bất cứ điều gì hashcode đã được tạo ra, chúng ta hãy đặt anh ở hashcode cộng thêm 1. Và nếu đó là đầy đủ cho phép của đưa anh vào hashcode cộng 2. Lợi ích của việc này là nếu anh ta không chính xác nơi chúng tôi nghĩ rằng ông là, và chúng ta phải bắt đầu tìm kiếm, có lẽ chúng ta không cần phải đi quá xa. Có lẽ chúng ta không cần phải tìm kiếm tất cả các yếu tố n của bảng băm. Có lẽ chúng ta phải tìm kiếm một vài trong số họ. 

Và vì vậy chúng tôi vẫn chăm sóc theo hướng mà trường hợp trung bình là gần 1 vs gần n, vì vậy có lẽ đó sẽ làm việc. Vì vậy, chúng ta hãy xem cách này có thể làm việc trong thực tế. Và chúng ta hãy xem nếu có thể chúng ta có thể phát hiện các vấn đề có thể xảy ra ở đây. 

Hãy nói rằng chúng tôi băm Bart. Vì vậy, bây giờ chúng tôi đang đi để chạy một bộ mới của chuỗi thông qua các hàm băm, và chúng tôi chạy Bart qua băm chức năng, chúng tôi nhận được hashcode 6. Chúng ta hãy xem, chúng ta thấy là 6 trống rỗng, vì vậy chúng tôi có thể đặt Bart có. 

Bây giờ chúng ta băm Lisa và rằng cũng tạo ra hashcode 6. Vâng bây giờ mà chúng tôi đang sử dụng này phương pháp, chúng tôi bắt đầu vào lúc 6 tuyến tính thăm dò, chúng ta thấy rằng 6 là đầy đủ. Chúng tôi không thể đặt Lisa trong 6. Vì vậy, nơi nào chúng ta đi? Hãy đi đến 7. 7 sản phẩm nào, vì vậy mà các công trình. Vì vậy, chúng ta hãy đặt Lisa có. 

Bây giờ chúng ta băm Homer và chúng tôi có được 7. OK, chúng tôi cũng biết rằng 7 đầy đủ bây giờ, vì vậy chúng tôi không thể đặt Homer có. Vì vậy, chúng ta hãy đi đến 8. 8 có sẵn? Yeah, và gần 8 thành 7, do đó, nếu chúng ta phải bắt đầu tìm kiếm chúng tôi sẽ không phải đi quá xa. Và như vậy chúng ta hãy đặt Homer lúc 8. 

Bây giờ chúng ta băm Maggie và trả về 3, cảm ơn lòng tốt chúng tôi có thể chỉ cần đặt Maggie có. Chúng tôi không phải làm bất kỳ loại thăm dò cho rằng. Bây giờ chúng ta băm Marge, và Marge cũng trả 6. 

Vâng 6 là đầy đủ, 7 là đầy đủ, 8 là đầy đủ, 9, tất cả phải cảm tạ Thiên Chúa, 9 là trống rỗng. Tôi có thể đặt Marge lúc 9. Đã chúng tôi có thể thấy rằng chúng ta đang bắt đầu có vấn đề này mà hiện nay chúng tôi bắt đầu căng ra loại điều của xa mã băm của họ. Và đó theta của 1, trung bình mà Nếu là hằng số thời gian, đang bắt đầu để có được một chút more-- bắt đầu có xu hướng nhiều hơn một chút hướng theta của n. Chúng tôi đang bắt đầu đánh mất điều đó lợi thế của bảng băm. 

Vấn đề này chúng ta chỉ nhìn thấy là một cái gì đó gọi là clustering. Và những gì là thực sự xấu về Clustering là một khi bạn bây giờ có hai yếu tố đó là mặt bằng bên kia nó làm cho nó thậm chí nhiều khả năng, bạn có gấp đôi cơ hội, rằng bạn đang đi có va chạm khác với cụm đó, và các cluster sẽ phát triển một. Và bạn sẽ tiếp tục tăng trưởng và phát triển khả năng của bạn có một vụ va chạm. Và cuối cùng nó chỉ là xấu như không phân loại dữ liệu ở tất cả. 

Các vấn đề khác là mặc dù chúng tôi vẫn còn, và cho đến nay cho đến thời điểm này, chúng tôi đã chỉ được loại hiểu biết những gì một bảng băm là, chúng ta vẫn chỉ có chỗ cho 10 dây. Nếu chúng ta muốn tiếp tục băm các công dân của Springfield, chúng ta chỉ có thể nhận được 10 trong số họ trong đó. Và nếu chúng ta cố gắng và thêm một lần thứ 11 hoặc 12, chúng ta không có một nơi để đặt chúng. Chúng tôi chỉ có thể quay xung quanh trong vòng tròn cố gắng để tìm một chỗ trống, và chúng tôi có thể bị mắc kẹt trong một vòng lặp vô hạn. 

Vì vậy, loại này mượn ý tưởng của một cái gì đó gọi là chuỗi. Và đây là nơi mà chúng ta sẽ mang lại danh sách liên kết lại thành hình ảnh. Điều gì nếu thay vì lưu trữ chỉ các dữ liệu chính nó trong mảng, mọi phần tử của mảng có thể giữ nhiều mẩu dữ liệu? Vâng đó không có ý nghĩa, phải không? Chúng ta biết rằng một mảng chỉ có thể hold-- mỗi phần tử của một mảng chỉ có thể giữ một mảnh các dữ liệu của các kiểu dữ liệu. 

Nhưng nếu những gì mà kiểu dữ liệu là một danh sách liên kết, phải không? Vì vậy, những gì nếu mỗi phần tử của mảng là một con trỏ đến đầu của một danh sách liên kết? Và sau đó chúng ta có thể xây dựng những danh sách liên kết và phát triển chúng tùy tiện, vì danh sách liên kết cho phép chúng ta lớn lên và thu nhỏ hơn rất nhiều linh hoạt hơn so với một mảng nào. Vì vậy, nếu chúng ta bây giờ sử dụng, chúng tôi tận dụng điều này, phải không? Chúng tôi bắt đầu phát triển các chuỗi ra khỏi các vị trí mảng. 

Bây giờ chúng ta có thể phù hợp với một vô hạn lượng dữ liệu, hoặc phải là vô hạn, một số lượng tùy ý dữ liệu, vào bảng băm của chúng tôi mà không bao giờ chạy vào các vấn đề của vụ va chạm. Chúng tôi cũng đã loại bỏ phân nhóm bằng cách làm này. Và cũng chúng tôi biết rằng khi chúng ta chèn vào một danh sách liên kết, nếu bạn gọi lại từ video của chúng tôi trên danh sách liên kết đơn lẻ danh sách liên kết và danh sách liên kết kép, đó là một thời gian hoạt động liên tục. Chúng tôi chỉ cần thêm vào phía trước. 

Và cho cái nhìn lên, cũng chúng tôi biết mà nhìn lên trong một danh sách liên kết có thể là một vấn đề, phải không? Chúng ta phải tìm kiếm thông qua nó từ đầu đến cuối. Không ngẫu nhiên truy cập vào một danh sách liên kết. Nhưng nếu thay vì có một liên kết danh sách nơi mà một tra cứu sẽ là O của n, Hiện tại chúng tôi có 10 danh sách liên kết, hoặc 1.000 danh sách liên kết, bây giờ nó là O của n chia cho 10, hoặc O của n khi chia cho 1000. 

Và trong khi chúng tôi đang nói chuyện lý thuyết về sự phức tạp chúng ta bỏ qua các hằng số, trong thực tế thế giới những điều thực sự quan trọng, bên phải? Chúng tôi thực sự sẽ thông báo rằng điều này sẽ xảy ra chạy 10 lần nhanh hơn, hoặc nhanh hơn 1.000 lần, bởi vì chúng tôi đang phân phối một dài chuỗi trên 1.000 chuỗi nhỏ hơn. Và do đó, mỗi lần chúng tôi phải tìm kiếm thông qua một trong những chuỗi chúng ta có thể bỏ qua 999 chuỗi chúng ta không quan tâm về, và chỉ cần tìm kiếm một. 

Mà là trên trung bình thể ngắn hơn khoảng 1.000 lần. Và vì vậy chúng tôi vẫn là loại chăm sóc đối với trường hợp này trung bình của thời gian là không đổi, nhưng chỉ bởi vì chúng ta đang tận dụng phân chia bởi một số yếu tố không đổi rất lớn. Chúng ta hãy xem làm thế nào điều này có thể thực sự nhìn mặc dù. Vì vậy, đây là bảng băm chúng tôi đã có trước khi chúng tôi tuyên bố một bảng băm là khả năng lưu trữ 10 dây. Chúng tôi sẽ không làm điều đó nữa. Chúng tôi đã biết hạn chế của phương pháp đó. Bây giờ bảng băm của chúng tôi sẽ là một mảng của 10 nút, con trỏ cho người đứng đầu của danh sách liên kết. 

Và ngay bây giờ nó là null. Mỗi một trong những 10 con trỏ là null. Không có gì ở chúng tôi băm bảng ngay bây giờ. 

Bây giờ chúng ta hãy bắt đầu đưa một số thứ vào bảng băm này. Và chúng ta hãy xem làm thế nào phương pháp này là sẽ có lợi cho chúng ta một chút. Bây giờ chúng ta băm Joey. Chúng tôi sẽ sẽ chạy chuỗi Joey qua một hàm băm và chúng tôi trở lại 6. Vâng chúng ta làm gì bây giờ? 

Vâng bây giờ làm việc với các danh sách liên kết, chúng tôi không làm việc với mảng. Và khi chúng tôi đang làm việc với danh sách liên kết chúng tôi biết chúng ta cần phải bắt đầu tự động phân bổ không gian và xây dựng dây chuyền. Đó là loại how-- những là cốt lõi các yếu tố của việc xây dựng một danh sách liên kết. Vì vậy, hãy động phân bổ không gian cho Joey, và sau đó chúng ta hãy thêm anh ấy vào chuỗi. 

Vì vậy, bây giờ nhìn những gì chúng tôi đã làm. Khi chúng ta băm Joey chúng tôi đã nhận hashcode 6. Bây giờ con trỏ tại vị trí mảng 6 chỉ vào đầu của một danh sách liên kết, và ngay bây giờ nó chỉ yếu tố của một danh sách liên kết. Và các nút trong đó danh sách liên kết là Joey. 

Vì vậy, nếu chúng ta cần phải nhìn lên Joey sau đó, chúng ta chỉ băm Joey một lần nữa, chúng tôi nhận được 6 lần nữa bởi vì chúng tôi hàm băm là xác định. Và sau đó chúng tôi bắt đầu từ đầu của danh sách liên kết chỉ đến vị trí của mảng 6, và chúng tôi có thể lặp qua đó cố gắng tìm Joey. Và nếu chúng ta xây dựng của chúng tôi băm bảng hiệu quả, và hàm băm của chúng tôi hiệu quả để phân phối dữ liệu tốt, trung bình mỗi người trong những liên kết danh sách tại mỗi địa điểm mảng sẽ là 1/10 kích thước của nếu chúng ta chỉ có nó như là một lớn duy nhất danh sách liên kết với tất cả mọi thứ trong đó. 

Nếu chúng tôi phân phối là rất lớn liên quan danh sách trên 10 danh sách liên kết mỗi danh sách sẽ là 1/10 kích thước. Và như vậy 10 lần nhanh hơn để tìm kiếm thông qua. Vì vậy, hãy làm điều này một lần nữa. Bây giờ chúng ta băm Ross. 

Và giả Ross, khi chúng ta làm điều đó mã băm chúng tôi nhận lại là 2. Vâng bây giờ chúng tôi tự động phân bổ một nút mới, chúng tôi đặt Ross ở nút đó, và chúng tôi nói bây giờ mảng vị trí 2, thay vì chỉ để null, chỉ vào đầu của một liên kết danh sách mà chỉ có nút là Ross. Và chúng ta có thể làm thêm một thời gian này, chúng tôi có thể băm Rachel và nhận được hashcode 4. malloc một nút mới, đưa Rachel trong nút, và nói một vị trí mảng 4 bây giờ chỉ vào đầu của một danh sách liên kết mà chỉ yếu tố sẽ xảy ra là Rachel. 

OK, nhưng những gì sẽ xảy ra nếu chúng ta có một vụ va chạm? Hãy xem cách chúng tôi xử lý va chạm sử dụng các phương pháp chaining riêng biệt. Hãy băm Phoebe. Chúng tôi nhận được hashcode 6. Trong ví dụ trước, chúng tôi đã chỉ lưu trữ các chuỗi trong mảng. Đây là một vấn đề. 

Chúng tôi không muốn clobber Joey, và chúng tôi đã đã thấy rằng chúng ta có thể nhận được một số phân nhóm vấn đề nếu chúng ta cố gắng và bước thông qua và thăm dò. Nhưng nếu chúng ta chỉ cần loại điều trị này theo cùng một cách, phải không? Nó giống như thêm một phần tử cho người đứng đầu của một danh sách liên kết. Hãy gian chỉ malloc cho Phoebe. 

Chúng tôi sẽ nói con trỏ trỏ tới của Phoebe cho người đứng đầu cũ của danh sách liên kết, và sau đó 6 chỉ trỏ tới đứng đầu mới của danh sách liên kết. Và bây giờ nhìn, chúng tôi đã thay đổi Phoebe trong. Bây giờ chúng ta có thể lưu trữ hai các yếu tố với hashcode 6, và chúng tôi không có bất kỳ vấn đề. 

Đó là khá nhiều tất cả có tới loạt. Và chắc chắn là chaining phương pháp phù hợp sẽ có hiệu quả nhất cho bạn nếu bạn đang lưu trữ dữ liệu trong một bảng băm. Nhưng sự kết hợp của mảng và danh sách liên kết với nhau để tạo thành một bảng băm thực sự cải thiện đáng kể khả năng của bạn để lưu trữ một lượng lớn dữ liệu, và rất nhanh chóng và hiệu quả tìm kiếm thông qua các dữ liệu đó. 

Vẫn có một nhiều hơn cấu trúc dữ liệu ra có mà thậm chí có thể là một chút tốt hơn về bảo đảm rằng chúng ta chèn, xóa, và nhìn lên lần thậm chí còn nhanh hơn. Và chúng ta sẽ thấy rằng trong một đoạn video trên cố gắng. Tôi Doug Lloyd, đây là CS50.