• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

hashmap

 
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I have an assignment that involves a hash map that I would like to review.
The HashMap has a load factor of .75
Initial array size of 13
Items are added in the order they appear

The items to be added in this order are:

Item >>Hashcode >> Computed modulus
Patriots >>1342415383 >> 10
Steelers >>700056533 >> 7
Chargers >>330628742 >> 2
Texans >>532139483 >> 5
Packers >>217142585 >> 10
49ers >>2112979549 >> 5
Saints >>207265348 >> 4
Giants >>1631149803 >> 4

I am assuming Since there are 8 items and load factor is .75 the array could have 9 items added before it needs to be resized.
I attached a pdf of the diagrams of the 2 conditions we were suppose to model, Separate Chaining hashing with an linked list and Quadratic probing.
With the Quadratic probing I did not know whether or not each collision starts with k+1 or is the quadratic cumulative?
For example:
item one is in index 3
item two is in index 3 therefore it goes in k+1 (3+1) or index 4
If item three goes in index 4 do you compute its new location with k+1 again or k+2 squared.
When I did my problem I started at k+1 for each new collision.

I was not sure how to get the diagram in the body of the post. hope the attachment works


Untitled-1.png
[Thumbnail for Untitled-1.png]
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Stop worrying about the internals of classes. You don't need to know it.
 
mark cortez
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Stop worrying about the internals of classes. You don't need to know it.




I do, it was the assignment to worry about it.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Right. Stop writing hashcodes in decimal. Write them in hexadecimal.

A hash map is based around an array of Map.Entry<K, V> objects. The size of that array is always an exact power of 2. So you cannot have a 13‑element array; it will be enlarged to 16. The hashcode is fiddled to move any variability to the right (that is called rehashing), then the little formula
h & c − 1
is applied. That is not quite a remainder function (in non‑English‑speaking countries they say modulo) because it can never return a negative result. It matches the array indices exactly when h=hashcode and c=capacity=array size, and array size can be exactly defined by 2. If you have a 16‑element array, the result of that little formula is the same as the rightmost hex digit in the hashcode, after rehashing. You can see that easily if you write in hexadecimal.
Also, you not will reach the default load factor after 9 entries. The default size for a hash map is 16 and the default load factor is 75%, so using (13, 0.75f) will give you exactly the same as the default, and you reach the load factor at 12 entries.
You cannot predict which “bucket” a particular K goes into because of the rehashing.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

mark cortez wrote: . . .
I do, it was the assignment to worry about it.

Please explain more.

If your assignment thinks that this ever uses a 13‑element array, it is mistaken.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

A few minutes ago, I wrote: . . . You cannot predict which “bucket” a particular K goes into because of the rehashing.

Well, you can download the source code and look at the rehashing algorithm, but you won't want to do your own rehashing.

Again, it is the sort of thing which you can only readily do if you write hashcodes in hexadecimal.
 
Author
Posts: 285
12
Scala IntelliJ IDE Netbeans IDE Python Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think your question is misplaced (i.e. in the wrong forum.) This is, I believe, a question about (a college classwork assignment on the topic of) "Algorithms". That's not the same as "using the Java class called HashMap", and for sure not "Beginning Java" in any case

Meanwhile, I find the question intriguing and worthwhile, and realize I need to brush up on some long forgotten stuff that, as other commentators have observed, regular day to day programmers tend not to worry about!
 
mark cortez
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:Right. Stop writing hashcodes in decimal. Write them in hexadecimal.



I was given the hashcodes, I computed the modulo.

Campbell Ritchie wrote: If you have a 16‑element array, the result of that little formula is the same as the rightmost hex digit in the hashcode, after rehashing. You can see that easily if you write in hexadecimal.
Also, you not will reach the default load factor after 9 entries. The default size for a hash map is 16 and the default load factor is 75%, so using (13, 0.75f) will give you exactly the same as the default, and you reach the load factor at 12 entries



The professors instructions stated that it is an " initial array size of 13". Also the threshold is to be calculated on the number of items present and not the indexes that are filled and that the array will only resize when the next item added equals the threshold size. I do not believe the diagram should have 16 indexes even if it the default. As far writing in hexadecimal formatt, we have not covered that.

I am fairly confident in the diagram that illustrates separate chaining hashing but i was not ably to determine was the quadratic probing.
For example:
item one is in index 3
item two is in index 3 therefore it goes in k+1 (3+1) or index 4
If item three goes in index 4 do you compute its new location with k+1 again or k+2 squared.
When I did my problem I started at k+1 for each new collision.
If I am making no sense then I will rethink the problem.
 
mark cortez
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Simon Roberts wrote:I think your question is misplaced (i.e. in the wrong forum.) This is, I believe, a question about (a college classwork assignment on the topic of) "Algorithms". That's not the same as "using the Java class called HashMap", and for sure not "Beginning Java" in any case

Meanwhile, I find the question intriguing and worthwhile, and realize I need to brush up on some long forgotten stuff that, as other commentators have observed, regular day to day programmers tend not to worry about!


I think this is correct
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If I have completely misunderstood the question, thinking it was about the Java® built-in class, I am so sorry.
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I looked up quadratic probing and found this.
 
mark cortez
Greenhorn
Posts: 16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:I looked up quadratic probing and found this.


np,
I am assuming after the first collision you rest the function back to k+1squared. I was not able to find anything that said how it functions after it place the item. I can only assume that means that it starts right back at k+1 squared.
 
Simon Roberts
Author
Posts: 285
12
Scala IntelliJ IDE Netbeans IDE Python Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

mark cortez wrote:
With the Quadratic probing I did not know whether or not each collision starts with k+1 or is the quadratic cumulative?
For example:
item one is in index 3
item two is in index 3 therefore it goes in k+1 (3+1) or index 4
If item three goes in index 4 do you compute its new location with k+1 again or k+2 squared.
When I did my problem I started at k+1 for each new collision.



OK, I dug a text book out (Data Structures, Koffman & Wolfgang, 7-3, page 378), and I'm satisfied that your approach is correct. With quadratic probing, for each new attempt to insert an item, and given that the item has hashcode H, you will:

try the appropriate cell based on the (H mod tablesize).
If it's full, try the cell indicated by ((H + 1) mod tablesize)
then, if that's full, try ((H + 4) mod tablesize)
proceed by the progression of (H + (n^2) mod tablesize) until you succeed or fail to find a cell (I note that your load factor of 0.75 is insufficient to guarantee success, as I believe the requirement with quadratic probing is a load factor < 0.5 in addition to a prime table size)

Anyway, I think is what you're describing, although I'm always loath to trust algebra to operator precedence (so I included explicit parentheses) and I note that you omitted the explicit "mod tablesize" part in some of this.

So, yeah, I think you'll get the marks for the assignment

HTH,
Simon
 
Campbell Ritchie
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Simon Roberts wrote:I think your question is . . . in the wrong forum. . . .

I think you are right. Algorithms probably belong in the “General Computing” forum, so let's try there.
 
Straws are for suckers. Now suck on this tiny ad!
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic