Tristan Elliott

Posted on

# My notes on Cyclic Shift hash codes in Kotlin

### Resources

• `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:
``````class SortedEmoteMap {

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`

### 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,
``````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
}

``````
• 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.