Concurrent Skip List Map

Before we start I would like to thanks all of you that have subscribed to my blog. We have reached 2,000 subscribers!!! As a matter of fact, we currently have 2,150 subscribers. Thanks a lot!!!

It is so hard to find real news not politically opinionated. For example, I ran into an article that discussed the AztraZeneca vaccine trial in the UK. Apparently there have been two cases in which people that received the vaccine got severely ill. In both cases the trial stopped until further investigation. In both cases it was determined that the issue was not associated with the vaccine. The trials continued in the UK.

In the USA, some scientists decided that they should receive more information including genetic material from the patients affected. Due to privacy reasons the additional requested data was denied. The article continues to blame the USA administration for not being able to get what they requested.

One should understand that there are different trials going on many different countries for the AztraZeneca and other COVID-19 vaccines. It is up to each country to decide which vaccines will be approved for their use. If the UK approves a vaccine, that does not imply that the USA should approve it or not. We need to conduct our own tests, collect data and make an educated decision.

Vaccines in general are not 100% free of side effects. Authorities, your physician and finally you need to make an educated decision. Educated does not mean political or for some reason opinionated. You need to get as much reliable data as possible and then make the educated decision.

Do you know that the yearly flu vaccines that most people get once a year have the possibility of giving you the Guillain-Barré syndrome? The chances are about 1 in 1000000 (that is one million). My wife and I used to get the flu vaccine every year. About a decade or so ago, we both got the flu shots. No problem with my wife. A couple days after receiving the vaccine, I could not see straight. One of my eyes was looking upwards while the other downwards. This started about three days before a scheduled trip for a winter vacation outside the US. My wife drove me to Mayo clinic in Rochester, Minnesota. I was examined by several specialists. Within 24 hours I was able to drive. We were able to take off on holiday. When I got back, I was feeling very well like nothing had happened. That was the last year we got flu shots.

For the COVID-19 pandemic vaccine, we will wait for several products to become available and for a few months to go by before we get vaccinated. This is just a precaution. We do not have a problem working from home and shopping for groceries a couple times a month. We hope that sometime next year, we will get a vaccine.

Today we will cover an implementation in Java for a type of hash table. If interested, I have used the Java HashMap class in many posts in my blog. In general you define a key : value pair and insert it into an instance of the hash map. When you need the value, you present the key to the hash map, and are able to get back the value. This data structure behaves quite similar to a directory of phone book. In the case of a phone book, you provide the name and the phone book returns the associated phone number.

Java and other programming languages provide different flavors of hash map classes. They all behave somewhat different because they are intended to be used to address different type of problems.

For example, let’s assume we have a list of values in a table in ascending order and wish to locate an entry in order to read back the associated value. We could use an array to hold the list of key : value pairs and perform a binary search. Depending on the size of the table, and the frequency of use, our solution might be not optimal. A binary search is typically an O(log(n)) which is faster than a linear search O(n). If we need to operate at O(1) time complexity we need to use a hash map.

In some cases that is all we would need, but in others such approach may or may not work well. For example, let’s assume we have our list of keys sorted in ascending order. The list is sparse, meaning that the keys are not in a monotonically ascending order, they are somewhat sparse e.g., {3, 5, 9, 10, 14, 17, … , 255}. If all the keys are always present, then a hash map will work, but what if some new keys may be inserted and some existing keys may be deleted. When you access your hash map you may or may not find what you are looking for.

We will cover this subject in further depth with a real world example and will see why different hash map classes are made available. For now let’s get familiar with the Java class ConcurrentSkipListMap.

11,360

main <<< K: 11 V: 360
main <<< i: 0 (8,202)
main <<< i: 1 (6,126)
main <<< i: 2 (6,299)
main <<< i: 3 (1,59)
main <<< i: 4 (9,41)
main <<< i: 5 (3,175)
main <<< i: 6 (10,287)
main <<< i: 7 (2,359)
main <<< i: 8 (7,208)
main <<< i: 9 (3,355)
main <<< i: 10 (6,59)
main <<< slm.size: 8
main <<<      slm: {1=59, 2=359, 3=355, 6=59, 7=208, 8=202, 9=41, 10=287}

main <<<   equals: true
main <<<   equals: false

getNextValue <<< randKey: 6
getNextValue <<< nextKey: 6
main <<<  randKey: 6 nextValue: 59

main <<<  removed: 59
main <<<  removed: 359
main <<<  removed: 355
main <<<  removed: 59
main <<<  removed: 208
main <<<      slm: {8=202, 9=41, 10=287}

main <<<  removed: 287
main <<<  removed: 41
main <<<  removed: 202
main <<< slm.size: 0
main <<<      slm: {}


11,360

main <<< K: 11 V: 360
main <<< i: 0 (6,140)
main <<< i: 1 (10,233)
main <<< i: 2 (1,306)
main <<< i: 3 (3,302)
main <<< i: 4 (10,262)
main <<< i: 5 (6,122)
main <<< i: 6 (3,120)
main <<< i: 7 (8,222)
main <<< i: 8 (3,94)
main <<< i: 9 (8,82)
main <<< i: 10 (7,12)
main <<< slm.size: 6
main <<<      slm: {1=306, 3=94, 6=122, 7=12, 8=82, 10=262}

main <<<   equals: true
main <<<   equals: false

getNextValue <<< randKey: 0
getNextValue <<< nextKey: 1
main <<<  randKey: 0 nextValue: 306

main <<<  removed: 306
main <<<  removed: 94
main <<<  removed: 122
main <<<  removed: 12
main <<<  removed: 82
main <<<      slm: {10=262}

main <<<  removed: 262
main <<< slm.size: 0
main <<<      slm: {}

We have two examples. We provide two numbers and that program does some processing. Some results are displayed. All this will become clear when we see the actual source code in Java that I wrote on a Windows 10 machine using the VSCode IDE.

It seems that we assign the integers to two variables K and V. Looks that we enter a loop and assign random key values to random values and store them in some type of hash map.

We then display the size of the hash map and the values. Note that we seem to have inserted 11 values but the hash map only has eight. The reason for this is that some keys have been duplicated. Note that the last value for a duplicate key is stored. The last write overwrites previous values.

Next we will check something for equality.

We then seem to provide a random key and get back the associated value. If you look at key 6 in the map which we named slm, the associated value is 59. That seems to make sense.

It seems that we remove some key : value pairs in ascending order and the rest in descending order.

The second example uses the same set of values 11 and 30. Since the keys and values appear to be randomly generated they are different from the previous run. It also looks like we has two additional collisions between keys because the final hash map only contains six key : value pairs.

We continue looking until we get to the call of the getNextValue() function. It seems that the program provides a random key with a value of zero (0), but as we can verify, out hash map does not contain a key with value zero (0). Somehow the function was able to use the next higher key, in this case one (1) and return the value 306.

Now let’s take a look at the main code.

    /**
     * Test scaffolding
     */
    public static void main(String[] args) {

        // **** open scanner ****
        Scanner sc = new Scanner(System.in);

        // **** read number of keys and maximum value ****
        String[] strs = sc.nextLine().split(",");

        // **** close scanner ****
        sc.close();

        // **** ****
        int K = Integer.parseInt(strs[0]);
        int V = Integer.parseInt(strs[1]);

        // **** ****
        System.out.println("main <<< K: " + K + " V: " + V);

        // **** instantiate list map ****
        ConcurrentSkipListMap<Integer, Integer> slm = new ConcurrentSkipListMap<Integer, Integer>();

        // **** to generate random integers for the keys and values ****
        Random rand = new Random();

        // **** loop populating the list map ****
        for (int i = 0; i < K; i++) {

            // **** generate random key:value pair ****
            int key     = rand.nextInt(K);
            int value   = rand.nextInt(V);

            // **** display key:value pair ****
            System.out.println("main <<< i: " + i + " (" + key + "," + value + ")");

            // **** put the pair in the list map ****
            slm.put(key, value);
        }

        // **** display the list map ****
        System.out.println("main <<< slm.size: " + slm.size());
        System.out.println("main <<<      slm: " + slm.toString());
        System.out.println();

        // **** check if the list maps match ****
         System.out.println("main <<<   equals: " + slm.equals(slm));
         System.out.println("main <<<   equals: " + slm.equals(new ConcurrentSkipListMap<Integer, Integer>()));
         System.out.println();

        // **** generate a random key ****
        int randKey = rand.nextInt(K);

        // **** get associated value ****
        int nextValue = getNextValue(randKey, slm);

        // **** display the result ****
        System.out.println("main <<<  randKey: " + randKey + " nextValue: " + nextValue);
        System.out.println();

        // **** remove some values from the list map ****
        for (int i = 0; i < K / 2; i++) {

            // **** get the first key ****
            int key = slm.firstKey();

            // **** remove the key ****
            int removed = slm.remove(key);

            // **** display the key ****
            System.out.println("main <<<  removed: " + removed);
        }

        // **** display the list map ****
        System.out.println("main <<<      slm: " + slm.toString());
        System.out.println();

        // **** remove the rest of the keys in the list map ****
        while (!slm.isEmpty()) {

            // **** key the largest key in the list map ****
            Integer key = slm.lowerKey(K);
            if (key == null)
                break;

            // **** remove the key ****
            int removed = slm.remove(key);

            // **** display the key ****
            System.out.println("main <<<  removed: " + removed);
        }

        // **** display the list map ****
        System.out.println("main <<< slm.size: " + slm.size());
        System.out.println("main <<<      slm: " + slm.toString());
        
    }

We read the values for K and V. We initialize a ConcurrentSkipListMap object and a random generator.

Next we loop generating random keys and random values. These are put into the list map.

We display the size of the list map and the key : value pairs. Looks like we got a handle of how this class behaves.

Nest we get into the main reason we selected this type of hash map. We generate a random key. The key may or may not be in the list map. We then call the getNextValue() function and it returns a value that is guaranteed to be in the list map unless the list map is empty. In the first example a key is found and the associated value is returned. In the second example, the next key is used to return a value. This operation is what we will be using in a future post when we implement the basis for a load balancer.

The rest of the code removes pairs from the list map in different ways. The reason for this is to see how servers that may process requests may go down and will no longer be available to do so.

    /**
     * Look up the key in the specified list map.
     * If not found look for the next largest key and return the value.
     * If not found, return the value associated with the lowest key.
     */
    static int getNextValue(int randKey, ConcurrentSkipListMap<Integer, Integer> slm) {

        // **** display the random key ****
        System.out.println("getNextValue <<< randKey: " + randKey);

        // ***** check if in the list map OR use the next larger key ****
        Integer nextKey = slm.ceilingKey(randKey);

        // **** no larger key found  ****
        if (nextKey == null) {

            // **** display a message ****
            System.out.println("getNextValue <<< nextKey is null");

            // **** go for the first key in the list map ****
            nextKey = slm.ceilingKey(0);
        }

        // **** display the values ****
        System.out.println("getNextValue <<< nextKey: " + nextKey);

        // **** return the value associated with this key ****
        return slm.get(nextKey);
    }

We get a random key. We check if the key of a larger one is available in the map list. If not available, because the value for the random key is larger than the largest key in our map list, we need to get to the smallest key and be able to use that value. In other words, we wrap around our map list and continue the search from the top of the list map.

We get the next key and return the associated value.

The entire code for this project can be found in my GitHub repository.

Hope to post this and be done before 11:00 AM CDT. I have a three hour Amazon presentation I want to watch.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address:  john.canessa@gmail.com. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 2150 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

Twitter:  @john_canessa

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.