Chapter 10 of Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia
TLDR(too long didn't read)
This function will create a reliable hash code for strings:
classSortedEmoteMap{funhashCodeCyclicShift(s:String):Int{varh=0for(iins.indices){h=(hshl5)or(hushr27)// 5-bit cyclic shift of the running sumh+=s[i].code// add in next character}returnh}}
The problem I am trying to solve
So recently I have ran into a problem where I need to keep track of the top 7 most recent emotes used by my user. I think the best solution is to create a custom map data structure. Particularly a sorted map data structure but that will be for another blog post.
What is a hash code and why are we creating one ?
A hash code is one part of a map's hash function. The goal of a hash code is to map a key(in my case a string representing an Emote's name) to an integer. Which is known as the hash code
Cyclic-shift hash code
technically speaking a Cyclic-shift is just a variant of a polynomial hash code but it just replaces all the mathematics with direct bit manipulation. The actual method of this hash code looks like this,
funhashCodeCyclicShift(s:String):Int{varh=0for(iins.indices){h=(hshl5)or(hushr27)// 5-bit cyclic shift of the running sumh+=s[i].code// add in next character}returnh}
So long story short we use the signed and unsigned bitwise operators, combined with the bitwise or operator to give us a consistent distribution of bits. If you are wondering why the numbers 5 and 27. It is to achieve an effective cyclic shift for a 32-bit integer. This ensures that every bit in the 32-bit integer is shifted exactly once.
Cant we just use the built in hashCode() function?
Yes you 1000% could.... but then you wouldn't get to learn about bit shifts!!!!
Conclusion
Thank you for taking the time out of your day to read this blog post of mine. If you have any questions or concerns please comment below or reach out to me on Twitter.
Top comments (0)
Subscribe
For further actions, you may consider blocking this person and/or reporting abuse
Top comments (0)