Bản đồ băm là cấu trúc dữ liệu trong đó dữ liệu được lưu trữ ở định dạng khóa và giá trị trong đó tất cả các khóa là duy nhất và đối với một khóa cụ thể, sẽ có một giá trị cụ thể
Trong một hashmap, trọng tâm chính là khóa vì thông qua khóa, chúng tôi sẽ có thể truy cập và chèn dữ liệu
Trước hết chúng ta cần làm quen với một số thuật ngữ
- mảng mảng. Một mảng/danh sách được sử dụng để lưu trữ và truy cập các phần tử
- hàm băm. Để chuyển đổi khóa thành một số nguyên để biết chính xác vị trí nhập khóa hoặc thông qua nơi khóa được truy cập
Hàm Hash sẽ chịu trách nhiệm về hai việc
- Mã Băm. Cung cấp một số nguyên lớn hơn kích thước nhóm
- chức năng nén. Nén số nguyên để vừa với giới hạn kích thước nhóm thông qua “% kích thước nhóm”
Nhưng để tránh lấy cùng một chỉ mục cho hai khóa khác nhau thông qua hàm băm để tránh va chạm, chúng ta có hai phương pháp
- Băm khép kín/xâu chuỗi riêng biệt. Lưu trữ nhiều phần tử tại một vị trí dưới dạng danh sách liên kết
- mở địa chỉ. Lưu trữ ở nơi khác nếu chỉ mục đã đầy
Chèn vào HashMap
class mapNode:
def __init__[self, key, value]:
self.key = key
self.value = value
self.next = None
class HashMap:
def __init__[self]:
self.bucketsize = 10
self.bucket = [None for i in range[self.bucketsize]]
self.count = 0
def mapSize[self]:
return self.count
def compression[self, hashcode]:
return [abs[hashcode] % [self.bucketsize]]
def insertion[self, key, value]:
hashcode = hash[key]
index = self.compression[hashcode]
head = self.bucket[index]
while head != None:
if head.key == key:
head.value = value
return
head = head.next
newnode = mapNode[key, value]
newnode.next = head
self.bucket[index] = newnode
self.count += 1
map = HashMap[]
map.insertion['abc', 5]
map.insertion['bca', 8]
print[map.mapSize[]]đầu ra
2
Trong đoạn mã được viết ở trên, trước tiên chúng ta đã khai báo một lớp nút sẽ chịu trách nhiệm tạo một nút mới có khóa và giá trị
Sau đó, chúng tôi đã tạo một hashmap với kích thước nhóm 10 ngay lập tức với tất cả các phần tử là Không có và số lượng là “0” vì không có phần tử nào
Tiến về phía trước, chúng ta có phương thức mapSize[] sẽ trả về kích thước của bản đồ và phương thức compression[] sẽ lấy mã băm và nén nó để phù hợp với kích thước nhóm
Sau đó, chúng ta có một phương thức insertion[] sẽ xử lý việc tạo mã băm và gán giá trị cho phần đầu mới sau khi được tạo và tăng số lượng tương ứng
Mỗi chỉ mục trong mảng có thể lưu trữ một cặp khóa-giá trị. Nếu bản đồ băm được triển khai bằng cách sử dụng chuỗi để giải quyết xung đột, thì mỗi chỉ mục có thể lưu trữ cấu trúc dữ liệu khác, chẳng hạn như danh sách được liên kết, lưu trữ tất cả các giá trị cho nhiều khóa băm vào cùng một chỉ mục
Bất cứ khi nào chúng tôi cố gắng triển khai một số loại logic tìm kiếm thông qua dữ liệu của mình, chúng tôi đều muốn nó hiệu quả. Điều này có thể không xảy ra trong các chương trình nhỏ nhưng với các ứng dụng lớn có cơ sở mã khổng lồ, thời gian tìm kiếm, xóa hoặc sửa đổi để chạy bất kỳ loại logic nào được cho là tối thiểu.
Từ điển trong Python được sử dụng để lưu trữ dữ liệu dưới dạng Key. cặp giá trị. Họ sử dụng một kỹ thuật gọi là Băm để thực hiện Thao tác TÌM KIẾM dựa trên thời gian gần như không phụ thuộc vào kích thước của từ điển
Cũng đọc. Hướng dẫn Từ điển Python [Dict]
Băm là gì?
Băm là một kỹ thuật được sử dụng để sắp xếp và sau đó lập chỉ mục cho bất kỳ loại dữ liệu nào. Băm cho phép chúng tôi lấy một lượng lớn dữ liệu hoặc đầu vào được lập chỉ mục và lưu trữ chúng trong không gian đầu ra ít hơn bằng cách sử dụng các khóa thường được tạo bằng thứ gọi là Hàm băm, về cơ bản là một số loại logic toán học được áp dụng cho dữ liệu đầu vào của chúng tôi dẫn đến một giá trị số
Giả sử chúng ta có ba chuỗi và chúng ta muốn lưu trữ chúng một cách hiệu quả bằng cách sử dụng một số logic toán học. Ở đây chúng tôi có chuỗi John, Peter và Carrie. Vì vậy, nếu bạn muốn lưu trữ chúng bằng cách sử dụng hàm băm, bước đầu tiên ở đây là chúng ta sẽ thay đổi các chuỗi này thành một số bằng cách sử dụng hàm băm nào đó
Nếu chúng ta sử dụng hàm băm để chuyển đổi các chuỗi này thành số, thì trước tiên chúng ta chuyển đổi từ John thành 10, sau đó chúng tôi chuyển đổi Peter. Nó được chuyển thành 5. Sau đó, chúng tôi đang tiếp tục chuyển đổi Carrie, sẽ là 11. Vì vậy, chúng tôi đã chuyển đổi chuỗi của mình thành số
Bây giờ bạn có thể quan tâm đến cách chuyển đổi và hàm Hash ở đây là gì và nó hoạt động như thế nào. Chúng tôi sẽ cố gắng hiểu điều đó hơn nữa trong bài viết
Hàm băm trong Python
Hàm Hash chịu trách nhiệm chuyển đổi các chuỗi này bằng cách sử dụng một số công thức thành số
Tiếp theo, chúng ta phải lưu trữ những con số này trong một số cấu trúc dữ liệu. Nếu chúng ta có một danh sách mảng hoặc python, có 12 ô trong đó như được hiển thị ở đây, bằng cách sử dụng các số được tạo bởi hàm băm này, chúng ta sẽ chèn các chuỗi này vào các mảng này
Vì vậy, đối với chuỗi đầu tiên, là John, chúng ta có 10. Chúng tôi sẽ chèn chuỗi John vào chỉ số 10 trong mảng này. Sau đó, chuỗi tiếp theo là Peter. Vì vậy, khi chúng tôi chuyển đổi nó thành số, nó trở thành 5
Chúng tôi sẽ chèn chuỗi Peter vào chỉ mục của 5. Bây giờ, từ tiếp theo là Carrie. Khi chúng tôi chuyển đổi Carrie bằng cách sử dụng hàm băm ở đây, nó sẽ trở thành 11. Vì vậy, chúng tôi sẽ chèn Carrie vào chỉ số 11 vào mảng này ở đây. Chúng tôi đã hoàn thành việc chuyển đổi các chuỗi này thành số nguyên và chúng tôi đang chèn các chuỗi này vào mảng này
Đọc hoặc truy cập dữ liệu bằng hàm băm
Bây giờ, câu hỏi là, nếu chúng ta muốn đọc dữ liệu từ mảng này ở đây, làm thế nào chúng ta có thể truy cập nó?
Một lần nữa, logic là như nhau. Ví dụ: nếu chúng tôi muốn truy cập John, điều đầu tiên chúng tôi sẽ làm là sử dụng hàm băm tương tự và chuyển đổi John thành số. Mỗi khi chúng tôi chuyển đổi cùng một chuỗi, kết quả sẽ giống nhau. Vì vậy, chúng tôi sẽ nhận được 10. Dựa trên chỉ số 10, chúng ta có thể truy cập phần tử này ở đây
Tại sao chúng ta cần Hashing?
Chúng tôi biết rằng việc truy cập một phần tử của mảng hoặc danh sách Python dựa trên chỉ mục của chúng mất độ phức tạp thời gian O[1]. Đây là lý do tại sao băm rất quan trọng trong việc tìm kiếm một giá trị nhất định trong cấu trúc dữ liệu. Làm như vậy, chúng ta có thể dễ dàng nhận biết chuỗi có nằm trong mảng này hay không
Giả sử chúng ta muốn phát triển một ứng dụng trong đó thao tác tìm kiếm được sử dụng nhiều và chúng ta muốn ứng dụng của mình hoạt động nhanh nhất có thể. Trong trường hợp này, chúng ta có thể sử dụng băm. Băm cũng hoạt động tốt hơn bất kỳ cấu trúc dữ liệu nào khác về mặt hoạt động tìm kiếm
thuật ngữ băm
- Hàm băm. Đó là logic hoặc công thức toán học có thể được sử dụng để ánh xạ kích thước tùy ý của dữ liệu đầu vào thành đầu ra có kích thước cố định hoặc nhỏ hơn
- Giá trị băm. Đó là giá trị được trả về bởi Hàm băm
- Bảng băm. Đó là cấu trúc dữ liệu triển khai kiểu dữ liệu trừu tượng mảng kết hợp và cấu trúc có thể ánh xạ khóa thành giá trị
- va chạm. Xung đột xảy ra khi hai khóa khác nhau của hàm băm tạo ra cùng một đầu ra
Triển khai HashMap trong Python
Hãy thử tìm hiểu tổng quan về Hashmap bằng cách triển khai một. Chúng ta sẽ tạo một Custom Class chứa các chức năng cơ bản. Sau đây là các chức năng có trong lớp tùy chỉnh của chúng tôi. Mã chứa chính nó có tất cả các giải thích mà chúng ta đã thảo luận trước đây trong bài viết
- _hash[bản thân, khóa]. Đây là Hàm băm được xác định của chúng tôi hoặc logic toán học mà chúng tôi áp dụng cho khóa để chuyển đổi nó thành một giá trị tích phân
- đặt [bản thân, khóa, giá trị]. Chức năng này sẽ cho phép chúng tôi thêm một khóa. cặp giá trị vào Bản đồ băm của chúng tôi
- lấy [bản thân, chìa khóa]. Để lấy một giá trị cho khóa đã cho, chức năng này được sử dụng
- __str__[bản thân]. Để in ra Bản đồ băm hoàn chỉnh tới thiết bị đầu cuối của chúng tôi
class HashMap[object]:
def __init__[self, size]:
"""Initializing the list with the argument size for our HashMap"""
self.data = [[]] * [size]
def _hash[self, key]:
"""Hash Function:
marked as a private method in the Object"""
# Initialize
hash_value = 0
# Iterating and generating hashed values using the logic below
# Logic: Taking the initial value of 0 and adding to it the ASCII encoding for each character,
# and multiplying by the index value. After that we are taking the modulus of the result using the
# length of the array
# This becomes our hashed value i.e. the index position of the input to be placed
# in the output space
for i in range[len[key]]:
hash_value = [hash_value + ord[key[i]] * i] % len[self.data]
return hash_value
def set[self, key, value]:
# Represents the index position where we want to store our data
address = self._hash[key]
if not self.data[address]:
self.data[address] = []
# If there is a collision of index value i.e. our hashed value
# then simply add on to that array
self.data[address].append[[key, value]]
return self.data
def get[self, key]:
# Getting the hashed value again, with the same hash function to locate the value
# for the given key
address = self._hash[key]
# assigning the entire array to a variable in-order to operate later
currentBucket = self.data[address]
if currentBucket:
# Iterating over the entire list to get the value
for i in range[len[currentBucket]]:
# Check to retrieve the value
if currentBucket[i][0] == key:
# If found, return the current bucket
return currentBucket[i][1]
# If no value present
return "Data Not Found"
# In order to print the hashmap to see the structure
def __str__[self]:
return "".join[str[item] for item in self.data]
# Instantiating from our Object Class with 50 buckets
myHash = HashMap[50]
# Setting the values to the hash table
myHash.set["john", 123]
myHash.set["peter", 567]
myHash.set["carrie", 898]
# Printing the entire hash table
print[myHash]
# Getting the values from the hash table using the keys
print[myHash.get["john"]] # Output: 123
print[myHash.get["guava"]] # Output: Data Not Found
đầu raPhần kết luận
Trong bài viết này, chúng tôi đã giới thiệu các thuật ngữ chính và phương pháp để tạo Hash Map bằng Python. Như tên cho thấy, nó giống như việc tạo một bản đồ bằng cách sử dụng dữ liệu để cung cấp sự trừu tượng hóa về logic cơ bản để biểu diễn. Chúng cung cấp một cách hiệu quả để hiển thị và định vị các giá trị dựa trên các khóa cũng như để chèn và xóa các giá trị dựa trên các khóa