CollisionlessStringCache.java

public class CollisionlessStringCache implements StringCache {

    private Node[] nodes;
    private int size;

    public StringCache(int size) {
        this.nodes = new Node[size];
        this.size = size;
    }

    @Override
    public String get(char[] chars, int length) {
        int hash = hashCode(chars, length);
        int bucket = (hash & Integer.MAX_VALUE) % size;

        Node node = nodes[bucket];
        if (node == null) {
            nodes[bucket] = new Node(new String(chars, 0, length), hash);
            return nodes[bucket].string;
        } else {
            Node prev = node;
            while (node != null) {
                if (node.equals(chars, length, hash)) {
                    return node.string;
                }
                prev = node;
                node = node.next;
            }
            prev.next = new Node(new String(chars, 0, length), hash);
            return prev.next.string;
        }
    }

    private int hashCode(char[] chars, int length) {
        // Implementation taken from String.hashCode()
        int hash = 0;
        for (int i=0; i<length; i++) {
            hash = 31*hash + chars[i];
        }
        return hash;
    }

    private static class Node {

        private String string;
        private int hash;
        private Node next;

        public Node(String string, int hash) {
            this.string = string;
            this.hash = hash;
        }

        public boolean equals(char[] chars, int length, int hash) {
            if (hash != this.hash || length != string.length()) {
                return false;
            }
            for (int i=0; i<length; i++) {
                if (string.charAt(i) != chars[i]) {
                    return false;
                }
            }
            return true;
        }

    }

}