Table of contents
Resources
TLDR
The problem I am trying to solve
Cyclic-shift hash code
Cant we just use the built in hashCode() function
My app on the Google play store
Chapter 10 of Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia
This function will create a reliable hash code for strings:
fun hashCodeCyclicShift(s:String):Int{
var h = 0
for (i in s.indices) {
h = (h shl 5) or (h ushr 27) // 5-bit cyclic shift of the running sum
h += s[i].code // add in next character
}
return h
}
}
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
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,
var h = 0
for (i in s.indices) {
h = (h shl 5) or (h ushr 27) // 5-bit cyclic shift of the running sum
h += s[i].code // add in next character
}
return h
}
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.
