IT/Software career thread: Invert binary trees for dollars.

A

a_skeleton_06

<Banned>
1,923
2,410
I had a co-worker who would come in and shoot off a few emails and then go to the movie theater to catch a movie, get some lunch, come back and show his face and then dip back out again. I don't think any of the management even noticed.
 
T

Tenks

Bronze Knight of the Realm
14,163
606
Cad said:
The keys themselves are stored in a tree of some kind, right?
Click to expand...

No the keys get hashed via hashCode on the Key object. This then gets stored in what they like to call a bucket which is basically the hash of the Key. If there is a hash collision then multiple keys are stored in the same bucket and popped into a linked list. For retrieval if a bucket has multiple keys it will then iterate over the items in the bucket and call equals() on the items to verify you're getting the proper item. So even if AA and Bb generate the same hashCode once the get() method is called on the HashMap it will seek to the right bucket then iterate over calling .equals() until it finds if you're getting AA or Bb and then return that keys' value. This is why you don't want to blindly start overwriting hashCode and equals on Objects since it can greatly impact performance inside of a HashMap.
 
Cad

Cad

<Bronze Donator>
24,487
45,378
Tenks said:
No the keys get hashed via hashCode on the Key object. This then gets stored in what they like to call a bucket which is basically the hash of the Key. If there is a hash collision then multiple keys are stored in the same bucket and popped into a linked list. For retrieval if a bucket has multiple keys it will then iterate over the items in the bucket and call equals() on the items to verify you're getting the proper item. So even if AA and Bb generate the same hashCode once the get() method is called on the HashMap it will seek to the right bucket then iterate over calling .equals() until it finds if you're getting AA or Bb and then return that keys' value. This is why you don't want to blindly start overwriting hashCode and equals on Objects since it can greatly impact performance inside of a HashMap.
Click to expand...

Right, I'm talking about the buckets. Are the buckets just stored in an array? When it hashes does it just iterate over the buckets until it matches, then iterate over the keys calling equals() ?

For a very large number of buckets seems like it should store those in a search tree.
 
T

Tenks

Bronze Knight of the Realm
14,163
606
Cad said:
Right, I'm talking about the buckets. Are the buckets just stored in an array? When it hashes does it just iterate over the buckets until it matches, then iterate over the keys calling equals() ?

For a very large number of buckets seems like it should store those in a search tree.
Click to expand...

Yes it is an array. Effectively the hash is the index in the array. Under the hood (looking at the code right now) it is a Node<K,V>[] and the Node is effectively the linked list which has an int hash, K key, V value and Node<K,V> next. So during retrieval it gets the Node from table[hash] (effectively, there is some complication here.) If the Node returned here passes equality check it returns it. If not then it starts iterating the LinkedList.

I'm not seeing how a BST would really help here since there is no real searching. It seeks to the general ballpark with the hash and then iterates for equality.
 
wormie

Asshat wormie

2023 Asshat Award Winner
<Gold Donor>
16,820
30,964
Cad said:
Right, I'm talking about the buckets. Are the buckets just stored in an array? When it hashes does it just iterate over the buckets until it matches, then iterate over the keys calling equals() ?

For a very large number of buckets seems like it should store those in a search tree.
Click to expand...
Eh its usually just an array.

edit: too slow
 
Cad

Cad

<Bronze Donator>
24,487
45,378
Tenks said:
Yes it is an array. Effectively the hash is the index in the array. Under the hood (looking at the code right now) it is a Node<K,V>[] and the Node is effectively the linked list which has an int hash, K key, V value and Node<K,V> next. So during retrieval it gets the Node from table[hash] (effectively, there is some complication here.) If the Node returned here passes equality check it returns it. If not then it starts iterating the LinkedList.

I'm not seeing how a BST would really help here since there is no real searching. It seeks to the general ballpark with the hash and then iterates for equality.
Click to expand...

Cool I was picturing that differently. From my quick googling it looks like Java 8 changed the hash collisions so that if there's a large number in one bucket it'll use a red-black tree. But thats not really what I was referring to so I can't claim correctness on that. :)

Thanks, love to geek out now and then with what my day job is now...
 
Nija

Nija

<Silver Donator>
1,916
3,730
If you can browse reddit you can also browse some kind of learning resource. Do that instead.
 
  • 1Like
  • 1Solidarity
Reactions: 1 users
nazon

nazon

Molten Core Raider
57
51
Noodleface said:
Because we can't work from home
Click to expand...

I am in the same boat. I could easily do my entire job from home. Showing up in the morning and leaving at the end of the day isn't all bad. I have a few coworkers who show up to work already on a conference call, and they leave for the day on a conference call. They pretty much work 24/7. Without setting boundaries, these fools will drop dead in their early 50s, never having truly lived. That big retirement account won't mean much if you never retire.
 
Mist

Mist

Eeyore Enthusiast
<Gold Donor>
30,414
22,202
nazon said:
I have a few coworkers who show up to work already on a conference call, and they leave for the day on a conference call. They pretty much work 24/7. Without setting boundaries, these fools will drop dead in their early 50s, never having truly lived. That big retirement account won't mean much if you never retire.
Click to expand...
This exactly describes my life right now.
 
You must log in or register to reply here.