javalinked-listhashmapprobing

Do hash-maps initially put/get with polling or liked lists?

I am making a graphing function using a hashmap to store all the nodes. I know how hashing works, but for hashmaps, I do not know if they use lin/quad probing to put/get nodes, or if it is a linked list. I want it to use polling as I only want one node per hash and not a linked list format (or any other format that has multiple nodes hashed out to the same location). Is this how it is done normally or do I need to set some value to change the linked list method to a lin/quad probing method.

I am basically wanting to know if one of my nodes maps out to the same place in the map as a previous node,

  1. Will it replace the old node with the new node (deletion method for mapping), and if it does not replace then...

  2. Will it just attach it on to the end of a linked list at that space in memory containing both nodes or...

  3. Will it use some type of polling method to get a new location in the map that contains no new nodes

I only want one node in each available position in the map

Solution

  • I'm refering to the implementation of the HashMap in Java 8 (1.8.0_66-b18 to be specific).

    HashMap maintains a table of Nodes.

    When you put a value for a key, the key is hashed and mapped onto bucket (a node in a table) using table.length - 1 & hash as index.

    If there is no node at this index, a new one will be created.

    If there is a node at this index, either the value will be replaced (if we have the same key) or a new node will be appended. A bucket is organized as a structure of nodes. First it's linked list-like, but if the number of nodes becomes greater than certain threshold, it will be "treeified" i.e. converted to a tree-like structure.

    To answer your questions:

    1. No, it will not replace old node with a new node. If there is already a node for this key, its value will be replaced.
    2. Yes, a new node will be attached to the nodes structure (linked list-like or tree-like). Linked list-like structure may be consequently converted to a tree-like structure.
    3. No. Mapping the hash onto index of the table is hardcoded.

    I am basically wanting to know if one of my nodes maps out to the same place in the map as a previous node

    You can't be sure about this without digging into internals of HashMap (which are private). The minimally invasive is probably to find out capacity/length of the table of the HashMap, and the calculate indices for hashes of each of the keys. But even capacity() is not accessible. So this is a pretty good indication that it is an implementation details and you should not really do it.

    You also can hardly influence whether you'll get just one node per bucket or more. It's not even hash collision, it is a collision of indices which HashMap calculates for the hash. The only way you don't get this collision is if:

    Which is pretty hard to guarantee.