Redis Internals: Dict

Dictionary is a data structure for storing key-value pair. Each key in a dictionary is unique and has a corresponding value. Redis implements its own dictionary and use it for hash key. As a data structure in server side, dictionary must take memory into consideration. That’s the reason why resizing and rehashing are so significant. ...

Nov 15, 2018 · 9 min · xgugeng

Redis Internals: List

Redis provides a generic doubly linked list implementation, which is widely used in Redis. If a list key involves two many elements or there are many long strings in the list, Redis will apply linked list for it. Publish-subscribe, slow query, monitor also make use of linked list. Redis keeps the states of clients in linked list, and client’s output buffer use it too. This post will plough into the implementation of doubly linked list. ...

Nov 6, 2018 · 6 min · xgugeng

Redis Internals: SDS

C string is used only for literal constant in Redis. For the situation that the string can be modified, Redis provide a Simple Dynamic String(SDS). The key in Redis is actually a SDS, and if you insert a key-value with SET msg "hello world", a SDS instance will be constructed for the key. In this case, the value is also a SDS instance with the content of “hello world”. Besides string, SDS is also used for buffer which can serve the AOF module and client’s input. This post will dive into the implementation of SDS comparing with classic C string. ...

Nov 1, 2018 · 8 min · xgugeng

Differences between Hashtable and HashMap

As I mentioned before, it is vital to read code with prepared questions. Hum, How about reading code with answers? The differences between Hashtable and HashMap have been explained many times including, null key & null value synchronized or not Enumeration and Iterator hash method I am wondering how these arguments are supported by code. This post will give a view of code illustrating the above confusion. ...

Aug 5, 2016 · 6 min · xgugeng

Java HashSet

For those who has no patience to look through this post, I conclude it in a word: HashSet is backed by HashMap. Set is a collection in which every element is unique. So does the keys in HashMap. It is reasonable to infer that the implementation of HashSet is based on HashMap, so it is. Remember resize of HashMap? it makes no guarantees as to the iteration order of the set. With the help of HashMap, HashSet offers constant time performance for the basic operations, like add, remove, contains and size. Iterating over this set requires time proportional to the sum of the HashSet instance’s size (the number of elements) plus the “capacity” of the backing HashMap instance (the number of buckets). ...

Aug 1, 2016 · 2 min · xgugeng

Java TreeMap

After joining the workforce, I have coded with various programming languages, like C++, Objective-C, Ruby, Python, Scala, Java, Go, etc. I ask to myself spontaneously, which language am I most skillful at? This question dismay me because I cannot answer it immediately. Since I choice to focus on Big Data, it’s pragmatic to equipped with Java and Python, two powerful weapons in this field. Reading the source code of java.util is a good start. The leading actor of this post is TreeMap, a Red-Black tree based NavigableMap implementation. It has no array underneath, as many of you think. Because TreeMap inherits directly AbstractMap, in contrast with LinkedHashMap. Performances differ on account of distinctive data structures. This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Now allow me to show you a close look. ...

Jun 12, 2016 · 6 min · xgugeng

Java LinkedHashMap

As its name implies, LinkedHashMap is a hash table and linked list implementation of the Map interface, with predictable iteration order. Different with HashMap, it maintains a doubly-linked list running through all of its entries, which also defines the iteration ordering, same as the order in which keys were inserted into the map. This order remains if a key is re-inserted into the map. Like HashMap, LinkedHashMap provides constant-time performance for the basic operations add, contains and remove, assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, Thanks to the linked list, this kind of map is well-suited to building LRU caches. So my questions is how LinkedHashMap preserves the linked list when key changes. ...

Jun 10, 2016 · 5 min · xgugeng

Java HashMap

It’s necessary to learn with questions. Otherwise, you may distract your focus when something you don’t know appears, whether should I go deeper or not. With preliminary doubts in your mind, this would not be a problem. Learning can be direct, clear and fruitful, which brings you more sense of achievement. For this post about the source code of HashMap, few questions need answers: data structure underneath why HashMap permits nulls and unsynchronized does it make guarantees as to the order of the map what happens when I put and get a key with value, and time complexity how the map shrink or expand when size changes ...

Jun 9, 2016 · 6 min · xgugeng

Java LinkedList

LinkedList is a doubly-linked list implementation of the List and Deque interfaces. By “doubly-linked”, it means we can traverse the list from the beginning to the end, and vice versa. This class is a member of Java Collections Framework, located in java.util. Let’s go straight to the source code. ...

Apr 18, 2016 · 5 min · xgugeng

Java String

String is one of the most common type of data in computer languages. A Java string is a series of characters gathered together, such as “abc”. Strings are constant, which means their value cannot be changed after created. This post introduces the basic of Java string, includes methods for examining individual characters of the sequence, for comparing strings, for searching strings, for extracting substrings and so on. ...

Apr 13, 2016 · 7 min · xgugeng