This discussion is archived
6 Replies Latest reply: Jan 21, 2013 3:35 PM by EJP RSS

HashMap Default Algorithm

800839 Newbie
Currently Being Moderated
Hi,

By default HashMap uses which algorithm to do the hashing as I found from the below link there are so many algorithms available?
Hence which is the default algorithm supported by HashMap and is there any possibility we can use the algorithm on our own
based on the requirement ? Please clarify.

Thanks.
  • 1. Re: HashMap Default Algorithm
    maheshguruswamy Journeyer
    Currently Being Moderated
    797836 wrote:
    Hi,

    By default HashMap uses which algorithm to do the hashing as I found from the below link there are so many algorithms available?
    Hence which is the default algorithm supported by HashMap and is there any possibility we can use the algorithm on our own
    based on the requirement ? Please clarify.

    Thanks.
    You can override hashcode() and implement your own, but HashMap adds in a second hash function which I don't think you can override. The end result is a hash which is derived from the output of the hashcode() method and the second internal hash function. My question is, why do you feel the need to override the hashing? Are you seeing collisions?
  • 2. Re: HashMap Default Algorithm
    800839 Newbie
    Currently Being Moderated
    Thanks Mahesh, But by default which algorithm HashMap uses?
  • 3. Re: HashMap Default Algorithm
    maheshguruswamy Journeyer
    Currently Being Moderated
    797836 wrote:
    Thanks Mahesh, But by default which algorithm HashMap uses?
    Just look at the source for HashMap.
  • 4. Re: HashMap Default Algorithm
    800839 Newbie
    Currently Being Moderated
    Thanks Mahesh

    This is the hash implementation, from i found that there are using Entry [] tables to avoid collision by creating a linked list of entries , where the collision nodes are put in the same bucket . But I am not gettiong whiich algorithm it internally uses , linear hashing? Please clarify and thanks for support.

    /**
    258 * Applies a supplemental hash function to a given hashCode, which
    259 * defends against poor quality hash functions. This is critical
    260 * because HashMap uses power-of-two length hash tables, that
    261 * otherwise encounter collisions for hashCodes that do not differ
    262 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
    263 */
    264 static int hash(int h) {
    265 // This function ensures that hashCodes that differ only by
    266 // constant multiples at each bit position have a bounded
    267 // number of collisions (approximately 8 at default load factor).
    268 h ^= (h >>> 20) ^ (h >>> 12);
    269 return h ^ (h >>> 7) ^ (h >>> 4);
    270 }
    271
  • 5. Re: HashMap Default Algorithm
    rp0428 Guru
    Currently Being Moderated
    >
    But I am not gettiong whiich algorithm it internally uses , linear hashing? Please clarify and thanks for support.
    >
    You still haven't said what difference it makes what algorithm Java uses.

    You can't change it. Your choices are to either use HashMap and its algorithm or write an implementation of your own.
  • 6. Re: HashMap Default Algorithm
    EJP Guru
    Currently Being Moderated
    I am not gettiong whiich algorithm it internally uses
    And you're not going to get it here. The people who wrote it aren't reading this,
    linear hashing?
    It isn't documented, not even in the source code. The nearest it gets is saying it uses power-of-two hash tables, which might or might not be linear hashing. Read the source code, as you have already been told.

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points