Xin chào các bạn, có bao giờ bạn tự hỏi làm thế nào mà từ điển Python có thể nhanh và đáng tin cậy như vậy không? . bảng băm
Biết cách hoạt động của bảng băm Python sẽ giúp bạn hiểu sâu hơn về cách thức hoạt động của từ điển và đây có thể là một lợi thế lớn cho sự hiểu biết về Python của bạn vì từ điển hầu như có ở khắp mọi nơi trong Python
Hàm băm
Trước khi giới thiệu bảng băm và cách triển khai Python của chúng, bạn phải biết hàm băm là gì và cách thức hoạt động của nó
Hàm băm là một hàm có thể ánh xạ một đoạn dữ liệu có độ dài bất kỳ thành một giá trị có độ dài cố định, được gọi là hàm băm
Các hàm băm có ba đặc điểm chính
- Họ tính toán nhanh. tính toán hàm băm của một phần dữ liệu phải là một thao tác nhanh
- Chúng mang tính quyết định. cùng một chuỗi sẽ luôn tạo ra cùng một hàm băm
- Chúng tạo ra các giá trị có độ dài cố định. không thành vấn đề nếu đầu vào của bạn là một, mười hay mười nghìn byte, hàm băm kết quả sẽ luôn có độ dài cố định, được xác định trước
Một đặc điểm khác khá phổ biến trong hàm băm là chúng thường là hàm một chiều. nhờ tính năng mất dữ liệu tự nguyện được triển khai trong hàm, bạn có thể lấy hàm băm từ một chuỗi nhưng bạn không thể lấy chuỗi gốc từ hàm băm. Đây không phải là tính năng bắt buộc đối với mọi hàm băm nhưng trở nên quan trọng khi chúng phải được bảo mật bằng mật mã
Một số thuật toán băm phổ biến là MD5, SHA-1, SHA-2, NTLM
Nếu bạn muốn tự mình thử một trong những thuật toán này, chỉ cần trỏ trình duyệt của bạn tới https. //www. md5online. org, chèn văn bản có độ dài bất kỳ vào hộp văn bản, nhấp vào nút
>>> hash["Bad Behaviour"]
7164800052134507161
Cách sử dụng phổ biến của băm
Có rất nhiều thứ dựa vào hàm băm và bảng băm chỉ là một trong số đó. Các cách sử dụng phổ biến khác của hàm băm là vì lý do mã hóa và bảo mật
Một ví dụ cụ thể về điều này là khi bạn cố tải xuống phần mềm mã nguồn mở từ internet. Thông thường, bạn cũng tìm thấy một tệp đồng hành là chữ ký của tệp. Chữ ký này chỉ là hàm băm của tệp gốc và nó rất hữu ích vì nếu bạn tự tính toán hàm băm của tệp gốc và kiểm tra nó với chữ ký mà trang web cung cấp, bạn có thể chắc chắn rằng tệp bạn đã tải xuống không có
Một cách sử dụng phổ biến khác của hàm băm là lưu trữ mật khẩu người dùng. Bạn đã bao giờ tự hỏi tại sao khi bạn quên mật khẩu của một trang web và bạn cố gắng khôi phục nó, trang web thường cho bạn chọn một mật khẩu khác thay vì trả lại cho bạn mật khẩu ban đầu mà bạn đã chọn?
Điều này được thực hiện vì lý do bảo mật vì nếu một số tin tặc có quyền truy cập vào cơ sở dữ liệu của trang web, họ sẽ không thể biết mật khẩu của bạn mà chỉ biết hàm băm của mật khẩu và vì hàm băm thường là hàm một chiều nên bạn có thể chắc chắn
Hàm >>> hash["Bad Behaviour"]
7164800052134507161
6 của Python
>>> hash["Bad Behaviour"]
7164800052134507161
Python có một hàm tích hợp để tạo hàm băm của một đối tượng, hàm
>>> hash["Bad Behaviour"]
7164800052134507161
Bên trong, hàm này gọi phương thức
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Bây giờ, hãy thử khởi động trình thông dịch Python và chơi với hàm
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash[1]
1
>>> hash[10]
10
>>> hash[10.00]
10
>>> hash[10.01]
230584300921368586
>>> hash[-10.01]
-230584300921368586
Nếu bạn thắc mắc tại sao các giá trị băm này dường như có độ dài khác nhau, hãy nhớ rằng hàm
>>> hash["Bad Behaviour"]
7164800052134507161
Như bạn có thể thấy, theo mặc định, giá trị băm của một giá trị số nguyên là chính giá trị đó. Lưu ý rằng điều này hoạt động bất kể loại giá trị bạn đang băm, vì vậy số nguyên
>>> hash[["R","e","a","l","P","y","t","h","o","n"]]
Traceback [most recent call last]:
File "", line 1, in
TypeError: unhashable type: 'list'
>>> hash[["R","e","a","l","P","y","t","h","o","n"]]
Traceback [most recent call last]:
File "", line 1, in
TypeError: unhashable type: 'list'
>>> hash[["R","e","a","l","P","y","t","h","o","n"]]
Traceback [most recent call last]:
File "", line 1, in
TypeError: unhashable type: 'list'
Có gì đặc biệt về điều này? . nếu hai đối tượng khác nhau có thể có cùng hàm băm, thì không thể thực hiện quy trình ngược lại bắt đầu từ hàm băm và quay lại đối tượng ban đầu. Trong trường hợp này, thông tin về loại đối tượng được băm ban đầu đã bị mất
Một vài điều thú vị khác mà bạn có thể lưu ý bằng cách băm số là số thập phân có giá trị băm khác với giá trị của chúng và giá trị âm có giá trị băm âm. Nhưng điều gì sẽ xảy ra nếu bạn cố gắng băm cùng một số mà bạn nhận được cho giá trị thập phân?
>>> hash["Bad Behaviour"]
7164800052134507161
Như bạn có thể thấy, hàm băm của số nguyên
>>> hash[["R","e","a","l","P","y","t","h","o","n"]]
Traceback [most recent call last]:
File "", line 1, in
TypeError: unhashable type: 'list'
>>> hash[["R","e","a","l","P","y","t","h","o","n"]]
Traceback [most recent call last]:
File "", line 1, in
TypeError: unhashable type: 'list'
Băm một chuỗi không khác nhiều so với băm một giá trị số. Bắt đầu trình thông dịch Python của bạn và thử băm một chuỗi
>>> hash["Bad Behaviour"]
7164800052134507161
Như bạn có thể thấy, một chuỗi có thể băm được và cũng tạo ra một giá trị số nhưng nếu bạn đã thử chạy lệnh này, bạn có thể thấy rằng trình thông dịch Python của bạn không trả về kết quả giống như ví dụ trên. Đó là bởi vì bắt đầu từ Python 3. 3 giá trị của các đối tượng chuỗi và byte được thêm vào một giá trị ngẫu nhiên trước quá trình băm. Điều này có nghĩa là giá trị của chuỗi được sửa đổi bằng một giá trị ngẫu nhiên thay đổi mỗi khi trình thông dịch của bạn bắt đầu, trước khi được băm. Nếu bạn muốn ghi đè hành vi này, bạn có thể đặt biến môi trường
>>> hash[["R","e","a","l","P","y","t","h","o","n"]]
Traceback [most recent call last]:
File "", line 1, in
TypeError: unhashable type: 'list'
Như bạn có thể mong đợi, đây là một tính năng bảo mật. Trước đó, bạn đã biết rằng các trang web thường lưu trữ hàm băm mật khẩu của bạn thay vì chính mật khẩu đó để ngăn chặn một cuộc tấn công vào cơ sở dữ liệu của trang web nhằm đánh cắp tất cả mật khẩu của trang web. Nếu một trang web chỉ lưu trữ hàm băm khi nó được tính toán thì kẻ tấn công có thể dễ dàng biết được mật khẩu ban đầu là gì. Họ chỉ cần lấy một danh sách lớn các mật khẩu thường được sử dụng [web có đầy những danh sách này] và tính toán hàm băm tương ứng của chúng để có được cái thường được gọi là bảng cầu vồng
Bằng cách sử dụng bảng cầu vồng, kẻ tấn công có thể không lấy được mọi mật khẩu trong cơ sở dữ liệu, nhưng vẫn có thể đánh cắp phần lớn trong số chúng. Để ngăn chặn kiểu tấn công này, một ý tưởng hay là thêm mật khẩu trước khi băm chúng, nghĩa là sửa đổi mật khẩu bằng một giá trị ngẫu nhiên trước khi tính toán hàm băm
Bắt đầu từ Python 3. 3 theo mặc định, trình thông dịch muối mọi đối tượng chuỗi và byte trước khi băm nó, ngăn chặn các cuộc tấn công DOS có thể xảy ra như Scott Crosby và Dan Wallach đã trình bày trên bài báo năm 2003 này
Tấn công DOS [trong đó DOS là viết tắt của từ chối dịch vụ] là một cuộc tấn công trong đó tài nguyên của hệ thống máy tính bị kẻ tấn công cố tình làm cạn kiệt để hệ thống không còn khả năng cung cấp dịch vụ cho khách hàng. Trong trường hợp cụ thể này của cuộc tấn công do Scott Crosby trình bày, cuộc tấn công có thể làm tràn ngập hệ thống mục tiêu với rất nhiều dữ liệu có xung đột băm, khiến hệ thống mục tiêu sử dụng nhiều sức mạnh tính toán hơn để giải quyết các xung đột
Các loại có thể băm Python
Vì vậy, tại thời điểm này, bạn có thể tự hỏi liệu có loại Python nào có thể băm được không. Câu trả lời cho câu hỏi này là không, theo mặc định, chỉ các loại bất biến mới có thể băm được trong Python. Trong trường hợp bạn đang sử dụng một bộ chứa bất biến [như bộ dữ liệu], thì nội dung cũng phải là bất biến để có thể băm được
Cố gắng lấy hàm băm của loại không thể băm trong Python, bạn sẽ nhận được ________ 88 từ trình thông dịch như trong ví dụ sau
________số 8Tuy nhiên, mọi đối tượng được xác định tùy chỉnh đều có thể băm trong Python và theo mặc định, hàm băm của nó được lấy từ id của nó. Điều đó có nghĩa là hai phiên bản khác nhau của cùng một lớp, theo mặc định có các giá trị băm khác nhau, như trong ví dụ sau
>>> hash["Bad Behaviour"]
7164800052134507161
Như bạn có thể thấy, theo mặc định, hai phiên bản khác nhau của cùng một đối tượng tùy chỉnh có các giá trị băm khác nhau. Tuy nhiên, hành vi này có thể được sửa đổi bằng cách triển khai phương thức
>>> hash["Bad Behaviour"]
7164800052134507161
Bảng băm
Bây giờ bạn đã biết hàm băm là gì, bạn có thể bắt đầu kiểm tra bảng băm. Bảng băm là một cấu trúc dữ liệu cho phép bạn lưu trữ một tập hợp các cặp khóa-giá trị
Trong bảng băm, khóa của mọi cặp khóa-giá trị phải có thể băm được, vì các cặp được lưu trữ được lập chỉ mục bằng cách sử dụng hàm băm của khóa của chúng. Các bảng băm rất hữu ích vì số lệnh trung bình cần thiết để tra cứu một phần tử của bảng không phụ thuộc vào số phần tử được lưu trữ trong chính bảng đó. Điều đó có nghĩa là ngay cả khi bảng của bạn tăng lên gấp mười hay mười nghìn lần, thì tốc độ tổng thể để tra cứu một phần tử cụ thể cũng không bị ảnh hưởng
Bảng băm thường được triển khai bằng cách tạo một số nhóm có thể chứa dữ liệu của bạn và lập chỉ mục dữ liệu này bằng cách băm các khóa của chúng. Giá trị băm của khóa sẽ xác định nhóm chính xác sẽ được sử dụng cho phần dữ liệu cụ thể đó
Trong ví dụ bên dưới, bạn có thể tìm thấy cách triển khai bảng băm cơ bản trong Python. Đây chỉ là một triển khai để cung cấp cho bạn ý tưởng về cách thức hoạt động của bảng băm vì như bạn sẽ biết sau này, trong Python, bạn không cần phải tạo triển khai bảng băm tùy chỉnh vì chúng được triển khai dưới dạng từ điển. Hãy xem cách triển khai này hoạt động
>>> hash["Bad Behaviour"]
7164800052134507161
Nhìn vào vòng lặp
>>> hash["Bad Behaviour"]
7164800052134507161
Hãy thử chạy ví dụ trên sau khi đặt biến môi trường
>>> hash[["R","e","a","l","P","y","t","h","o","n"]]
Traceback [most recent call last]:
File "", line 1, in
TypeError: unhashable type: 'list'
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Lưu ý rằng nếu bạn cố chạy chương trình mà chưa đặt biến
>>> hash[["R","e","a","l","P","y","t","h","o","n"]]
Traceback [most recent call last]:
File "", line 1, in
TypeError: unhashable type: 'list'
Trong ví dụ trên, bạn đã triển khai bảng băm Python lấy danh sách các bộ dữ liệu làm đầu vào và sắp xếp chúng thành một số nhóm bằng với độ dài của danh sách đầu vào bằng toán tử modulo để phân phối các giá trị băm trong bảng
Tuy nhiên, như bạn có thể thấy ở đầu ra, bạn có hai nhóm trống trong khi hai nhóm còn lại có hai giá trị khác nhau, mỗi nhóm có hai giá trị khác nhau. Khi điều này xảy ra, người ta nói rằng có xung đột trong bảng băm Python
Sử dụng hàm
>>> hash["Bad Behaviour"]
7164800052134507161
Hơn nữa, bạn càng tăng số lượng thùng bạn sẽ xử lý, bạn sẽ càng lãng phí nhiều không gian hơn. Để kiểm tra điều này, bạn chỉ cần thay đổi kích thước nhóm của ví dụ trước bằng cách sử dụng số lượng nhóm gấp hai lần độ dài của danh sách đầu vào
>>> hash["Bad Behaviour"]
7164800052134507161
Chạy ví dụ này, tôi đã kết thúc với việc phân phối dữ liệu đầu vào tốt hơn, tuy nhiên, tôi đã gặp sự cố và năm nhóm không sử dụng
>>> hash["Bad Behaviour"]
7164800052134507161
Như bạn có thể thấy, hai giá trị băm đã va chạm và đã được đưa vào cùng một nhóm
Vì xung đột thường không thể tránh khỏi, nên để triển khai bảng băm, bạn cũng cần triển khai phương pháp giải quyết xung đột. Các chiến lược phổ biến để giải quyết xung đột trong bảng băm là
- địa chỉ mở
- chuỗi riêng biệt
Chuỗi riêng biệt là chuỗi bạn đã triển khai trong ví dụ trên và bao gồm tạo chuỗi giá trị trong cùng một nhóm bằng cách sử dụng cấu trúc dữ liệu khác. Trong ví dụ đó, bạn đã sử dụng một danh sách lồng nhau phải được quét toàn bộ khi tìm kiếm một giá trị cụ thể trong một nhóm bị chiếm dụng quá mức
Trong chiến lược địa chỉ mở, nếu bộ chứa bạn nên sử dụng đang bận, bạn chỉ cần tiếp tục tìm kiếm một bộ chứa mới để sử dụng. Để triển khai giải pháp này, bạn cần thực hiện một vài thay đổi đối với cả cách bạn chỉ định bộ chứa cho các phần tử mới và cách bạn truy xuất giá trị cho một khóa. Bắt đầu từ hàm
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Như bạn có thể thấy, tất cả các nhóm được đặt thành giá trị mặc định
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Vì việc gán các nhóm bị thay đổi, nên quy trình truy xuất cũng sẽ thay đổi, bởi vì trong phương pháp
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Trong quá trình tra cứu, ở phương pháp
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Chạy ví dụ trên, khóa cho
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Vấn đề chính của chiến lược địa chỉ mở là nếu bạn phải xử lý cả việc xóa các phần tử trong bảng của mình, thì bạn cần thực hiện xóa logic thay vì xóa vật lý bởi vì nếu bạn xóa một giá trị đang chiếm một nhóm trong khi xung đột, giá trị kia
Trong ví dụ trước của chúng tôi,
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Vì vậy, khi sử dụng chiến lược địa chỉ mở, để xóa một phần tử, bạn phải thay thế bộ chứa của nó bằng một giá trị giả, giá trị này cho trình thông dịch biết rằng nó phải được coi là đã xóa để chèn mới nhưng được sử dụng cho mục đích truy xuất
từ điển. Triển khai bảng băm Python
Bây giờ bạn đã biết bảng băm là gì, hãy xem triển khai Python quan trọng nhất của chúng. từ điển. Từ điển trong Python được xây dựng bằng cách sử dụng bảng băm và phương pháp giải quyết xung đột địa chỉ mở
Như bạn đã biết, từ điển là một tập hợp các cặp khóa-giá trị, do đó, để xác định từ điển, bạn cần cung cấp danh sách các cặp khóa-giá trị được phân tách bằng dấu phẩy được đặt trong dấu ngoặc nhọn, như trong ví dụ sau
>>> hash["Bad Behaviour"]
7164800052134507161
Ở đây bạn đã tạo một từ điển có tên là
>>> hash["Bad Behaviour"]
7164800052134507161
Để truy xuất một giá trị cụ thể, bạn chỉ cần chỉ định khóa bằng dấu ngoặc vuông
>>> hash["Bad Behaviour"]
7164800052134507161
Nếu bạn cố gắng truy cập một phần tử không tồn tại, trình thông dịch Python sẽ đưa ra một ngoại lệ
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Để lặp lại toàn bộ từ điển, bạn có thể sử dụng phương thức
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Để lặp qua các khóa hoặc qua các giá trị của từ điển Python, bạn cũng có thể sử dụng các phương thức
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Để chèn một phần tử khác vào từ điển, bạn chỉ cần gán giá trị cho một khóa mới
>>> hash["Bad Behaviour"]
7164800052134507161
Để cập nhật giá trị của khóa hiện có, chỉ cần gán một giá trị khác cho khóa đã chèn trước đó
Xin lưu ý rằng vì từ điển được xây dựng trên đầu bảng băm, bạn chỉ có thể chèn một phần tử nếu khóa của nó có thể băm được. Nếu khóa của phần tử của bạn không thể băm được [chẳng hạn như danh sách], trình thông dịch sẽ đưa ra một ngoại lệ
>>> hash[["R","e","a","l","P","y","t","h","o","n"]]
Traceback [most recent call last]:
File "", line 1, in
TypeError: unhashable type: 'list'
>>> hash["Bad Behaviour"]
7164800052134507161
Để xóa một phần tử, bạn cần sử dụng câu lệnh
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Việc xóa một mục nhập không xóa giá trị thực trong từ điển, nó chỉ thay thế khóa bằng một giá trị giả để phương pháp giải quyết xung đột địa chỉ mở sẽ tiếp tục hoạt động, nhưng trình thông dịch sẽ xử lý tất cả sự phức tạp này cho bạn, bỏ qua phần tử đã xóa
Triển khai Pythonic của Bảng băm Python
Bây giờ bạn đã biết rằng từ điển là các bảng băm Python nhưng bạn có thể thắc mắc cách triển khai hoạt động ngầm, vì vậy trong chương này, tôi sẽ cố gắng cung cấp cho bạn một số thông tin về việc triển khai thực tế các Bảng băm Python
Hãy nhớ rằng thông tin tôi sẽ cung cấp ở đây dựa trên các phiên bản Python gần đây, bởi vì với Python 3. 6 từ điển đã thay đổi rất nhiều và giờ nhỏ hơn, nhanh hơn và thậm chí còn mạnh hơn, vì chúng hiện được sắp xếp theo thứ tự chèn [bảo đảm theo thứ tự chèn đã được triển khai trong Python 3. 6 nhưng đã được Guido chính thức công nhận trong Python 3. 7]
Hãy thử tạo một từ điển Python trống và kiểm tra kích thước của nó, bạn sẽ thấy rằng một từ điển Python trống chiếm 240 byte bộ nhớ
>>> hash["Bad Behaviour"]
7164800052134507161
Bằng cách chạy ví dụ này, bạn có thể thấy rằng chiếm dụng cơ bản của một từ điển Python là 240 byte. Nhưng điều gì sẽ xảy ra nếu bạn quyết định thêm một giá trị?
>>> hash["Bad Behaviour"]
7164800052134507161
Vì vậy, tại sao kích thước của từ điển không thay đổi? . 6 giá trị được lưu trữ trong một cấu trúc dữ liệu khác và từ điển chỉ chứa một con trỏ tới nơi lưu trữ giá trị thực. Hơn nữa, khi bạn tạo một từ điển trống, nó sẽ bắt đầu tạo Bảng băm Python với 8 nhóm chỉ dài 240 byte, vì vậy phần tử đầu tiên trong từ điển của chúng tôi hoàn toàn không thay đổi kích thước
Bây giờ hãy thử thêm một số thành phần khác và xem từ điển của bạn hoạt động như thế nào, bạn sẽ thấy từ điển phát triển
>>> hash["Bad Behaviour"]
7164800052134507161
Như bạn có thể thấy, dict đã lớn lên sau khi bạn chèn phần tử thứ sáu và thứ mười một, nhưng tại sao?
Bây giờ, hãy thử xóa tất cả các thành phần trong từ điển của bạn, từng cái một và khi bạn hoàn thành, hãy kiểm tra lại kích thước, bạn sẽ thấy rằng ngay cả khi từ điển trống, dung lượng vẫn chưa được giải phóng
>>> hash["Bad Behaviour"]
7164800052134507161
Điều này xảy ra bởi vì từ điển có dung lượng bộ nhớ thực sự nhỏ và việc xóa không thường xuyên khi làm việc với từ điển, trình thông dịch thích lãng phí một chút dung lượng hơn là tự động thay đổi kích thước từ điển sau mỗi lần xóa. Tuy nhiên, nếu bạn làm trống từ điển của mình bằng cách gọi phương thức
>>> hash["Bad Behaviour"]
7164800052134507161
>>> hash["Bad Behaviour"]
7164800052134507161
Như bạn có thể tưởng tượng, lần chèn đầu tiên vào từ điển này sẽ khiến trình thông dịch dành chỗ cho 8 nhóm, quay lại tình huống ban đầu
kết luận
Trong bài viết này, bạn đã tìm hiểu bảng băm là gì và chúng được triển khai như thế nào trong Python
Một phần lớn của bài viết này dựa trên bài phát biểu của Raymond Hettinger tại Pycon 2017
Raymond Hettinger là một nhà phát triển cốt lõi của Python và đóng góp của anh ấy cho sự phát triển của Python cho đến nay là vô giá