Fix #5293 - changed the way hashcode is improved in hash sets. #61
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
The hash code is further improved by using a special value in the hash sets called a `seed`. For sequential hash tables, this value depends on the size of the hash table. It determines the number of bits the hashcode should be rotated. This ensures that hash tables with different sizes use different bits to compute the position of the element. This way traversing the elements of the source hash table will yield them in the order where they had similar hashcodes (and hence, positions) in the source table, but different ones in the destination table. Ideally, in the future we want to be able to have a family of hash functions and assign a different hash function from that family to each hash table instance. That would statistically almost completely eliminate the possibility that the hash table element traversal causes excessive collisions. I should probably @mention extempore here.
szeiger
pushed a commit
to szeiger/scala
that referenced
this pull request
Mar 20, 2018
Dotty support
eed3si9n
added a commit
to eed3si9n/scala
that referenced
this pull request
May 14, 2019
FPORT: Avoid CCE when scalac internally uses compileLate
lrytz
pushed a commit
to lrytz/scala
that referenced
this pull request
Nov 5, 2019
FPORT: Avoid CCE when scalac internally uses compileLate Rewritten from sbt/zinc@768a3a8
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
The hash code is further improved by using a special value in the hash sets
called a
seed. For sequential hash tables, this value depends on the sizeof the hash table. It determines the number of bits the hashcode should be
rotated. This ensures that hash tables with different sizes use different
bits to compute the position of the element. This way traversing the elements
of the source hash table will yield them in the order where they had similar
hashcodes (and hence, positions) in the source table, but different ones in
the destination table.
Ideally, in the future we want to be able to have a family of hash functions
and assign a different hash function from that family to each hash table
instance. That would statistically almost completely eliminate the possibility
that the hash table element traversal causes excessive collisions.
I should probably @mention extempore here.