@Override
  public String intern(String s) {
    int h = s.hashCode();
    // In the future, it may be worth augmenting the string hash
    // if the lower bits need better distribution.
    int slot = h & (cache.length-1);

    Entry first = this.cache[slot];
    Entry nextToLast = null;

    int chainLength = 0;

    for(Entry e=first; e!=null; e=e.next) {
      if (e.hash == h && (e.str == s || e.str.compareTo(s)==0)) {
      // if (e.str == s || (e.hash == h && e.str.compareTo(s)==0)) {
        return e.str;
      }

      chainLength++;
      if (e.next != null) {
        nextToLast = e;
      }
    }

    // insertion-order cache: add new entry at head
    s = s.intern();
    this.cache[slot] = new Entry(s, h, first);
    if (chainLength >= maxChainLength) {
      // prune last entry
      nextToLast.next = null;
    }
    return s;
  }