234

I want to implement a HashMap in Python. I want to ask a user for an input. depending on his input I am retrieving some information from the HashMap. If the user enters a key of the HashMap, I would like to retrieve the corresponding value.

How do I implement this functionality in Python?

HashMap<String,String> streetno=new HashMap<String,String>();
   streetno.put("1", "Sachin Tendulkar");
   streetno.put("2", "Dravid");
   streetno.put("3","Sehwag");
   streetno.put("4","Laxman");
   streetno.put("5","Kohli")
0

11 Answers 11

377

Python dictionary is a built-in type that supports key-value pairs. It's the nearest builtin data structure relative to Java's HashMap.

You can declare a dict with key-value pairs set to values:

streetno = {
    "1": "Sachin Tendulkar",
    "2": "Dravid",
    "3": "Sehwag",
    "4": "Laxman",
    "5": "Kohli"
}

You can also set a key-value mapping after creation:

streetno = {}
streetno["1"] = "Sachin Tendulkar"
print(streetno["1"]) # => "Sachin Tendulkar"

Another way to create a dictionary is with the dict() builtin function, but this only works when your keys are valid identifiers:

streetno = dict(one="Sachin Tendulkar", two="Dravid")
print(streetno["one"]) # => "Sachin Tendulkar"
7
  • 21
    The second example just builds a dict in the same ways as before and then copies it. The other use dict, which would be more appopriate in this context, is dict(key1=value1, key2=value2, ...) but that requires the keys to strings which are also valid Python identifiers (and internally, this also creates a dictionary).
    – user395760
    Commented Jan 2, 2012 at 17:31
  • 1
    I'm not sure if I understand you correctly (what are "naked strings"?), but I believe you got it backwards. Your updated second example is invalid and I never intended to state something like that work. The keyword arguments syntax, which accepts only naked identifiers, internally uses a dictionary. The dict constructor supports keyword arguments and works like def dict(**kwds): return kwds if given keyword arguments.
    – user395760
    Commented Jan 2, 2012 at 17:39
  • 3
    Yeah, it looks like a "map" and it acts like a "map". But the question is not "Map in Python" but "Hash Map in Python": Are dictionaries a hash(!) map? Commented Jan 14, 2020 at 22:34
  • 1
    @user2661619 Yes. The underlying implementation of a dict uses a hash function to generate the address location of the item. The implementation is here: hg.python.org/cpython/file/10eea15880db/Objects/dictobject.c
    – Alan
    Commented Feb 1, 2020 at 20:16
  • 14
    Why don't you just tell me dictionary is hashmap
    – Dwa
    Commented Dec 23, 2020 at 17:50
41

All you wanted (at the time the question was originally asked) was a hint. Here's a hint: In Python, you can use dictionaries.

34

It's built-in for Python. See dictionaries.

Based on your example:

streetno = {"1": "Sachine Tendulkar",
            "2": "Dravid",
            "3": "Sehwag",
            "4": "Laxman",
            "5": "Kohli" }

You could then access it like so:

sachine = streetno["1"]

Also worth mentioning: it can use any non-mutable data type as a key. That is, it can use a tuple, boolean, or string as a key.

24

Hash maps are built-in in Python, they're called dictionaries:

streetno = {}                        #create a dictionary called streetno
streetno["1"] = "Sachin Tendulkar"   #assign value to key "1"

Usage:

"1" in streetno                      #check if key "1" is in streetno
streetno["1"]                        #get the value from key "1"

See the documentation for more information, e.g. built-in methods and so on. They're great, and very common in Python programs (unsurprisingly).

19
streetno = { 1 : "Sachin Tendulkar",
            2 : "Dravid",
            3 : "Sehwag",
            4 : "Laxman",
            5 : "Kohli" }

And to retrieve values:

name = streetno.get(3, "default value")

Or

name = streetno[3]

That's using number as keys, put quotes around the numbers to use strings as keys.

16

Here is the implementation of the Hash Map using python For the simplicity hash map is of a fixed size 16. This can be changed easily. Rehashing is out of scope of this code.

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None

class HashMap:
    def __init__(self):
        self.store = [None for _ in range(16)]
    def get(self, key):
        index = hash(key) & 15
        if self.store[index] is None:
            return None
        n = self.store[index]
        while True:
            if n.key == key:
                return n.value
            else:
                if n.next:
                    n = n.next
                else:
                    return None
    def put(self, key, value):
        nd = Node(key, value)
        index = hash(key) & 15
        n = self.store[index]
        if n is None:
            self.store[index] = nd
        else:
            if n.key == key:
                n.value = value
            else:
                while n.next:
                    if n.key == key:
                        n.value = value
                        return
                    else:
                        n = n.next
                n.next = nd

hm = HashMap()
hm.put("1", "sachin")
hm.put("2", "sehwag")
hm.put("3", "ganguly")
hm.put("4", "srinath")
hm.put("5", "kumble")
hm.put("6", "dhoni")
hm.put("7", "kohli")
hm.put("8", "pandya")
hm.put("9", "rohit")
hm.put("10", "dhawan")
hm.put("11", "shastri")
hm.put("12", "manjarekar")
hm.put("13", "gupta")
hm.put("14", "agarkar")
hm.put("15", "nehra")
hm.put("16", "gawaskar")
hm.put("17", "vengsarkar")
print(hm.get("1"))
print(hm.get("2"))
print(hm.get("3"))
print(hm.get("4"))
print(hm.get("5"))
print(hm.get("6"))
print(hm.get("7"))
print(hm.get("8"))
print(hm.get("9"))
print(hm.get("10"))
print(hm.get("11"))
print(hm.get("12"))
print(hm.get("13"))
print(hm.get("14"))
print(hm.get("15"))
print(hm.get("16"))
print(hm.get("17"))

Output:

sachin
sehwag
ganguly
srinath
kumble
dhoni
kohli
pandya
rohit
dhawan
shastri
manjarekar
gupta
agarkar
nehra
gawaskar
vengsarkar
2
  • I think your logic is partially correct! hash(key) & 15, 73%15= 13, but it's equivalent: 1001001 & 0001111 = 0001111 i.e 9 and not 13, I think using mod is the correct operation. Correct me if I am wrong!
    – Anu
    Commented Nov 14, 2018 at 17:17
  • How do you iterate through the list though?
    – Petro
    Commented Sep 30, 2019 at 16:55
11
class HashMap:
    def __init__(self):
        self.size = 64
        self.map = [None] * self.size

    def _get_hash(self, key):
        hash = 0

        for char in str(key):
            hash += ord(char)
        return hash % self.size

    def add(self, key, value):
        key_hash = self._get_hash(key)
        key_value = [key, value]

        if self.map[key_hash] is None:
            self.map[key_hash] = list([key_value])
            return True
        else:
            for pair in self.map[key_hash]:
                if pair[0] == key:
                    pair[1] = value
                    return True
                else:
                    self.map[key_hash].append(list([key_value]))
                    return True

    def get(self, key):
        key_hash = self._get_hash(key)
        if self.map[key_hash] is not None:
            for pair in self.map[key_hash]: 
                if pair[0] == key:
                    return pair[1]
        return None

    def delete(self, key):
        key_hash = self._get_hash(key)

        if self.map[key_hash] is None :
            return False
        for i in range(0, len(self.map[key_hash])):
            if self.map[key_hash][i][0] == key:
                self.map[key_hash].pop(i)
                return True

    def print(self):

        print('---Phonebook---')
        for item in self.map:
            if item is not None:
                print(str(item))

h = HashMap()
9

Python Counter is also a good option in this case:

from collections import Counter

counter = Counter(["Sachin Tendulkar", "Sachin Tendulkar", "other things"])

print(counter)

This returns a dict with the count of each element in the list:

Counter({'Sachin Tendulkar': 2, 'other things': 1})
1
  • 2
    I don't understand how this is an answer to the question. What you get here is a dictionary where names are keys and values are some counters (where did you get the input list from anyway?). While the question was looking for a hash map where unique keys point to names as values. Commented Aug 23, 2020 at 21:41
7

In python you would use a dictionary.

It is a very important type in python and often used.

You can create one easily by

name = {}

Dictionaries have many methods:

# add entries:
>>> name['first'] = 'John'
>>> name['second'] = 'Doe'
>>> name
{'first': 'John', 'second': 'Doe'}

# you can store all objects and datatypes as value in a dictionary
# as key you can use all objects and datatypes that are hashable
>>> name['list'] = ['list', 'inside', 'dict']
>>> name[1] = 1
>>> name
{'first': 'John', 'second': 'Doe', 1: 1, 'list': ['list', 'inside', 'dict']}

You can not influence the order of a dict.

4

A dictionary in Python is the best way to implement this. We can create the following dictionary using the given <key,value> pairs:

d = {"1": "Sachin Tendulkar", "2": "Dravid", "3": "Sehwag", "4": "Laxman", "5": "Kohli"}

To extract the value of a particular key, we can directly use d[key]:

name = d["1"] # The value of name would be "Sachin Tendulkar" here
1

That is my solution for LeetCode problem 706:

A hash map class with three methods: get, put and remove

class Item:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.next = None


class MyHashMap:

    def __init__(self, size=100):
        self.items = [None] * size
        self.size = size

    def _get_index(self, key):
        return hash(key) & self.size-1

    def put(self, key: int, value: int) -> None:
        index = self._get_index(key)
        item = self.items[index]
        if item is None:
            self.items[index] = Item(key, value)
        else:
            if item.key == key:
                item.value = value

            else:
                while True:
                    if item.key == key:
                        item.value = value
                        return
                    else:
                        if not item.next:
                            item.next = Item(key, value)
                            return
                        item = item.next



    def get(self, key: int) -> int:
        index = self._get_index(key)
            
        if self.items[index] is None:
            return -1
        item = self.items[index]
        while True:
            if item.key == key:
                return item.value
            else:
                if item.next:
                    item = item.next
                else:
                    return -1
        
        

    def remove(self, key: int) -> None:
        value = self.get(key)
        if value > -1:
            index = self._get_index(key)
            item = self.items[index]
            if item.key == key:
                self.items[index] = item.next if item.next else None
                return
                
            while True:
                if item.next and item.next.key == key:
                    item.next = item.next.next
                    return
                else:
                    if item.next:
                        item = item.next
                    else:
                        return

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.