-1

I have already read the following posts:

  1. How does the JVM check if a string is already in the string pool?

  2. How does Java implement string pooling?

Neither of them mentions the search algorithm that is used by the JVM to search for String literals that have previously been created and exist in the so-called "String pool."

chb
  • 1,727
  • 7
  • 25
  • 47
InterestinglyBored
  • 5
  • 5
  • 2
    Implementation-defined. Which implementation? – user202729 Jan 16 '18 at 05:05
  • You will need to refer to a specific implementation of the JVM, there are multiple popular ones ([List of Java virtual machines](https://en.wikipedia.org/wiki/List_of_Java_virtual_machines)). The one you get from Oracles official site as standard download is called [HotSpot](https://en.wikipedia.org/wiki/HotSpot). – Zabuzard Jan 16 '18 at 05:12
  • 1
    Hash table in HotSpot JVM – apangin Jan 16 '18 at 06:24

1 Answers1

1

The implementation of String pool is done in native language i.e. c/c++ using Java Native Interface (JNI) and shared libraries
You can read how to do this here
As per me, string pool has been implemented using trie data-structure
You can read about tries here

Trie will take O(l) ,where l is length of the requested string, time to search the string pool.

UPD1: The String pool has been implemented as a hash-table and the memory allocation to the pool can be updated using -XX:StringTableSize=<value>
Though i feel use of trie would have been better as trie would have accommodated more number of strings in the same space to that of a hash-table

swayamraina
  • 2,958
  • 26
  • 28
  • 1
    Why do you think it is `Trie`? Looks like some hash table is better solution. – talex Jan 16 '18 at 06:17
  • @talex the disadvantage of HotSpot’s string pool hash table is its fixed size, so there are lots of collision if the size has been exceeded, especially prior to Java 7, update 40, when the default size was as small as 1,023 (now its ~60,000). But the obvious disadvantage of the `Tri` as shown in that link is its dependency on the alphabet size, as a `char` can have 65536 different values… – Holger Jan 16 '18 at 09:57