While typing on my phone, I started getting curious about how the frequently used emojis feature is implemented. I was surprised that there wasn't some information out there about it (well, it is Apple, so not really), so it's time to put it out there!

The idea is that we have some set of n emojis, and we want to cache a subset of those emojis that are used the most. We could imagine attaching a usage count to each emoji, and saying that we want the k emojis with the highest count to be stored in this cache, with k <= n. Ideally, we want to be able to add to this cache and get elements from it in constant time.

Luckily for us, this is pretty trivial since this exact problem gets brought up in operating systems and there are a million solutions for it - see here.

First, we will implement an LFU cache in JavaScript. It will keep track of a few things. It will keep track of min, which is the smallest usage count currently in the cache. It has a capacity, which is the maximum amount of items that can exist in the cache. values is a Map that stores the key value pairs, counts stores each key and its respective usage count, and sets keeps track of each count and which keys have that count.

LFUCache constructor
1
class LFUCache {
2
    constructor(capacity){
3
        this.min = -1;
4
        this.capacity = capacity;
5
        this.values = new Map(); //stores keys and values
6
        this.counts = new Map(); //stores keys and access counts
7
        this.sets = new Map(); //Map<number, Set> - stores counts and a set of keys with that count
8
        this.sets.set(0, new Set());
9
    }

To get an element from the cache, we need to do a bit of bookkeeping each time.

Get an item
1
get(key){
2
    if(!this.values.has(key)){
3
        return -1;
4
    }
5
    let count = this.counts.get(key);
6
    if(count === undefined){
7
        throw new Error(`A key ${key} exists but has no count.`);
8
    }
9
    this.counts.set(key, count + 1);
10
    let set = this.sets.get(count);
11
    if(set === undefined){
12
        throw new Error(`A key ${key} exists but is not in a count set.`);
13
    }
14
    set.delete(key);
15
    if(count == this.min && set.size <= 0){
16
        this.min++;
17
    }
18
    if(!this.sets.has(count + 1)){
19
        this.sets.set(count + 1, new Set());
20
    }
21
    let newCountSet = this.sets.get(count + 1);
22
    newCountSet.add(key);
23
    return this.values.get(key);
24
}

We check that key exists in the cache, and continue accordingly. Then we update the count, and grab the count set that key is currently in. We move the element from that set to the set of one count higher, and create that set if needed. We also update the min, since we are changing the count of key. Finally, we return the value of key. Adding is about as simple:

Set an item
1
set(key, value){
2
    if(this.values.has(key)){
3
        this.values.set(key, value);
4
        this.get(key); //maintain ordering
5
        return;
6
    }
7
    if(this.values.size >= this.capacity){
8
        let evictSet = this.sets.get(this.min);
9
        let evictedKey = [...evictSet][0]; //get first element of set
10
        evictSet.delete(evictedKey);
11
        this.values.delete(evictedKey);
12
        this.counts.delete(evictedKey);
13
    }
14
    this.values.set(key, value);
15
    this.counts.set(key, 0);
16
    this.min = 0;
17
    let zeroCountSet = this.sets.get(0);
18
    zeroCountSet.add(key);
19
}

If key already exists in the cache, then we update the value and get the key, to reflect that it has been used again. Otherwise, if the cache is full, we have to figure out which element to evict. This is why we are keeping track of min - we can just get the count set that has the minimum count, since we are evicting the least frequently used item. We just take the first element from that set and remove it to make room for the new item. The nice thing about Set in JavaScript is that it maintains insertion order, so we are guaranteed that the first element in evictSet is the oldest. We also delete the evicted item from values and counts. Then, we initialize the new item in the cache, adding it to values and counts, and resetting min to 0, since the new item hasn't been accessed yet. Then, we add it to the count set of zero, and we are done! We have a data structure which maintains its elements in order of usage frequency, where items can both be added and retrieved in O(1) time.

Now, if we are going to use this in React, we are going to need to be able to get the elements as an array, so here is a short function to do that:

Convert to array
1
toList(ascending) {
2
  let res = []
3
  for (let set of this.sets.values()) {
4
    res = res.concat([...set])
5
  }
6
  if (ascending) {
7
    return res
8
  }
9
  return res.reverse()
10
}

This function simply iterates over sets and concats them onto a list. We pass in a parameter ascending to determine whether we want the list in ascending or descending order in terms of usage count.

Now that we have the data structure figured out, we can get to the emoji part. I'll make a simple React component to demonstrate.

Component state
1
function FrequentlyUsedEmojiExample() {
2
  const cache = useRef(new LFUCache(30))
3
  const [cachedEmojis, setCachedEmojis] = useState([])
4
  const [emojiInputs, setEmojiInputs] = useState('')

For hooks, we will just have two pieces of state - cachedEmojis, which are the emojis present in the cache, e.g. the most frequently used emojis. Also, we have emojiInputs which is just all of the emojis that have been inputted. cache is a LFUCache ref - it would be a good idea to abstract the cache away into a hook, but for simplicity we will just hold it in that ref.

Emoji component
1
const onEmojiInput = (emoji) => {
2
  setEmojiInputs(emojiInputs + emoji)
3
  cache.current.set(emoji, emoji) //emojis are just text so we don't need an identifier as the key
4
  setCachedEmojis(cache.current.toList(false))
5
}
6

7
const ClickableEmoji = (props) => {
8
  return (
9
    <>
10
      <Box
11
        userSelect={'none'}
12
        as={'span'}
13
        cursor={'pointer'}
14
        fontSize={'2xl'}
15
        onClick={() => onEmojiInput(props.emoji)}
16
        aria-label={
17
          'A clickable emoji - emojis in this dataset are not tagged, so further information about the content is unavailable.'
18
        }
19
      >
20
        {props.emoji}
21
      </Box>
22
    </>
23
  )
24
}

Here we have the emojis that can be used to add to the input. When an emoji is clicked, it just adds to emojiInputs, adds to cache, and refreshes the frequently used emojis stored in cachedEmojis. The rest of the component renders all of this stuff and looks like this:

Render the emojis
1
return (
2
  <>
3
    <Grid
4
      h={'100%'}
5
      gridTemplateColumns={'1fr 1fr'}
6
      gap={'0px 20px'}
7
      border={'1px'}
8
      p={'2'}
9
      mx={'auto'}
10
      overflowX={'scroll'}
11
      h={'300px'}
12
    >
13
      <GridItem textAlign={'center'}>
14
        <Heading as={'text'} size={'md'}>
15
          Frequently Used
16
        </Heading>
17
      </GridItem>
18
      <GridItem textAlign={'center'}>
19
        <Heading as={'text'} size={'md'}>
20
          All Emojis
21
        </Heading>
22
      </GridItem>
23
      <GridItem overflow={'scroll'} p={'2'}>
24
        <Grid templateColumns={'1fr 1fr 1fr 1fr'} gap={'10px'}>
25
          {cachedEmojis.map((emoji) => (
26
            <GridItem>
27
              <ClickableEmoji key={emoji} emoji={emoji} />
28
            </GridItem>
29
          ))}
30
        </Grid>
31
      </GridItem>
32
      <GridItem overflowY={'scroll'} p={'2'}>
33
        <Grid templateColumns={'1fr 1fr 1fr 1fr 1fr'} gap={'10px'}>
34
          {emojis.map((emoji) => (
35
            <GridItem>
36
              <ClickableEmoji key={emoji} emoji={emoji} />
37
            </GridItem>
38
          ))}
39
        </Grid>
40
      </GridItem>
41
    </Grid>
42
    <InputGroup maxW={'800px'} mt={'4'} mb={'8'} mx={'auto'}>
43
      <Input value={emojiInputs} fontSize={'2xl'} />
44
      <InputRightElement
45
        cursor={'pointer'}
46
        onClick={() => setEmojiInputs('')}
47
        readonly
48
      >
49
        <IoMdSend />
50
      </InputRightElement>
51
    </InputGroup>
52
  </>
53
)

It just creates a ChakraUI Grid which holds the frequently used emojis and the entire list of emojis, as well as a Input for the emoji input. And here it is in action!

Note: since this component just renders the emojis as text, it may look very janky depending on the browser and/or device you are viewing from. A better approach would be to render the emojis as <img> so that the width/height can be fixed.

Note that this doesn't behave exactly the same way as iOS or Android's frequently used emoji feature does. There are some UX enhancements that can be made - for example, if this emoji picker was put in a keyboard or a popup, deferring the cache refresh until it is closed so that the emojis don't move around while you are typing. The algorithm for determining what gets cached is also certainly more complex than this, but this is just meant to be a straightforward tutorial that shows how you can design a data structure and implement it in an interface. Hopefully you learned something, and if you made it all the way to the end, congratulations!!