Chúng ta có thể sử dụng Hashmap trong Python không?
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ể Show
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ữ
Hàm Hash sẽ chịu trách nhiệm về hai việc
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
Chèn vào HashMapclass 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 ra2 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 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 PythonHà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ămBâ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
Triển khai HashMap trong PythonHã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
Mã số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ậnTrong 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 HashMap được gọi bằng Python là gì?Trong Python, từ điển (hay gọi tắt là “dicts”) là một cấu trúc dữ liệu trung tâm. Dicts lưu trữ một số đối tượng tùy ý, mỗi đối tượng được xác định bằng một khóa từ điển duy nhất. Từ điển thường còn được gọi là bản đồ, hàm băm, bảng tra cứu hoặc mảng kết hợp .
Từ điển Python có phải là HashMap hay Hashtable không?Có, đó là ánh xạ băm hoặc bảng băm . Bạn có thể đọc mô tả về triển khai dict của python, như được viết bởi Tim Peters, tại đây. Bạn có thể đọc thêm về bảng băm hoặc kiểm tra xem nó đã được triển khai như thế nào trong python và tại sao nó được triển khai theo cách đó.
Có bảng băm trong Python không?Bảng Băm trong Python sử dụng mảng làm phương tiện lưu trữ và sử dụng phương thức băm để tạo chỉ mục nơi một phần tử sẽ được tìm kiếm từ đó hoặc cần được chèn vào . Nói cách khác, Bảng băm trong Python là cấu trúc dữ liệu lưu trữ dữ liệu bằng cách sử dụng một cặp giá trị và khóa.
HashMap và HashSet trong Python là gì?Sự khác biệt chính giữa HashSet và HashMap là hàm băm được sử dụng cho HashSet chỉ hoạt động trên một phần tử, trong khi đó, đối với HashMap, hàm này hoạt động trên hai phần tử. The new value will be overwritten on the previous value while insertion of new value in a HashMap with the key already existing. |