My notes on Cyclic Shift hash codes in Kotlin

Table of contents

1. Resources
2. TLDR
3. The problem I am trying to solve
4. Cyclic-shift hash code
5. Cant we just use the built in hashCode() function

My app on the Google play store

• The app

Resources

• 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:

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.