> For the complete documentation index, see [llms.txt](https://ondrej-kvasnovsky-2.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ondrej-kvasnovsky-2.gitbook.io/algorithms/data-structures/map.md).

# Map

Map stores values behind keys. That said, values in a map can be obtained using a key.

Lets create very simple hash map. This hash map is fixed size and does not count other types than integer.

```
class MyHashMap {

    Integer[] values = new Integer[1000000];

    /** Initialize your data structure here. */
    public MyHashMap() {
    }

    /** value will always be positive. */
    public void put(int key, int value) {
        values[hash(key)] = value;
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    public int get(int key) {
        Integer result = values[hash(key)];
        if (result == null) {
            return -1;
        }
        return result;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        values[hash(key)] = null;
    }

    private int hash(int value) {
        return values.length % value;
        // or we can use bit operator to limit number to upper boundary, which is length of array
        // return hashCode & (entries.length - 1);
        // hashCode: 10 , n: 9
        // hashCode (in binary): 1010 , n (in binary): 1001
        // position (in binary): 1000 (8 in decimal)
    }
}
```

Now we can use the hash map as follows.

```
MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);          // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found)
```

## Implementation using Entry

We need to use Entry class to handle duplicates (when two objects have the same hash code but they are not equal).

```
class HashMap<K, V> {
    private Entry[] entries;

    HashMap() {
        entries = new Entry[10];
    }

    public void put(K key, V value) {
        Entry<K, V> entry = new Entry<>(key, value);
        int position = calculateHashCode(key);
        if (entries[position] == null) {
            entries[position] = entry;
        } else {
            Entry<K, V> available = findNextAvailableEntry(position);
            available.next = entry;
        }
    }

    public V get(K key) {
        int position = calculateHashCode(key);
        Entry entry = entries[position];
        while (!entry.key.equals(key)) {
            entry = entry.next;
        }
        return (V) entry.value;
    }

    Entry<K, V> findNextAvailableEntry(int position) {
        Entry<K, V> current = entries[position];
        if (current.next != null) {
            current = current.next;
        }
        return current;
    }

    int calculateHashCode(K key) {
        return key.hashCode() % entries.length;
    }

    class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> next; // linked list

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
}
```

Lets try to use the hash map.

```
public class Test {

    public static void main(String... args) {
        HashMap<String, Integer> map = new HashMap<>();
        map.put("a", 1);
        map.put("b", 2);
        map.put("k", 3); // k has conflicting position 

        Integer one = map.get("a");
        System.out.println(one);

        Integer three = map.get("k");
        System.out.println(three);

        System.out.println("a: " + map.calculateHashCode("a"));
        System.out.println("b: " + map.calculateHashCode("b"));
        System.out.println("c: " + map.calculateHashCode("c"));
        System.out.println("d: " + map.calculateHashCode("d"));
        System.out.println("e: " + map.calculateHashCode("e"));
        System.out.println("f: " + map.calculateHashCode("f"));
        System.out.println("g: " + map.calculateHashCode("g"));
        System.out.println("h: " + map.calculateHashCode("h"));
        System.out.println("i: " + map.calculateHashCode("i"));
        System.out.println("j: " + map.calculateHashCode("j"));
        System.out.println("k: " + map.calculateHashCode("k"));
    }
}
```

How the position is calculated.

```
println "a".hashCode()
println "b".hashCode()
println "k".hashCode()
println "u".hashCode()

println "a".hashCode() % 10
println "k".hashCode() % 10
println "u".hashCode() % 10
```

Here is the output.

```
97
98
107
117

7
7
7
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://ondrej-kvasnovsky-2.gitbook.io/algorithms/data-structures/map.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.