patternjavaMinor
Java Trie Implementation
Viewed 0 times
implementationtriejava
Problem
I am creating a Trie class in Java, and am wondering what else can be done to make it even better. I am hoping to add concurrency to speed querying up.
public class Trie {
private HashMap root;
private final Character END_CHARACTER = ';
public Trie() {
initializeRoot();
}
public Trie(String s) {
initializeRoot();
add(s);
}
public Trie(Collection collection) {
initializeRoot();
for (String s : collection) {
add(s);
}
}
private void initializeRoot() {
root = new HashMap<>();
}
public void add(String s) {
HashMap node = root;
for (int i = 0; i ());
}
node = node.get(character);
}
node.put(END_CHARACTER, new HashMap<>());
}
public boolean contains(String s) {
HashMap node = root;
for (int i = 0; i < s.length(); i++) {
Character character = s.charAt(i);
if (node.containsKey(character)) {
node = node.get(character);
} else {
return false;
}
}
return node.containsKey(END_CHARACTER);
}
}Solution
Initializing
but we can do better.. let us take a look at
%%CODEBLOCK_2%%
If
Also if
%%CODEBLOCK_3%%
and call it
%%CODEBLOCK_4%%
But wait, we can do even better, as
%%CODEBLOCK_5%%
Finished ? No, we still can do better. As the passed String parameters won't be changed, let us make them
use interface types instead of the implementation
Putting altogether
```
public class Trie {
private final Map root = new HashMap<>();
private final Character END_CHARACTER = '$';
public Trie() {
}
public Trie(final String s) {
internalAdd(s);
}
public Trie(final Collection collection) {
for (String s : collection) {
internalAdd(s);
}
}
public void add(final String s) {
internalAdd(s);
}
private void internalAdd(final String s) {
Map node = root;
for (int i = 0; i ());
}
private void internalAdd(final String s, Map node) {
for (int i = 0; i ());
node = node.get(character);
}
}
public boolean contains(final String s) {
Map node = root;
for (int i = 0; i < s.length(); i++) {
if (node.isEmpty()) {
return false;
}
Character character = s.charAt(i);
if (node.containsKey(character)) {
node = node.get(character);
} else {
return false;
}
}
return node.contains; public Trie() {} public Trie(String s) { add(s); } public Trie(Collection collection) { for (String s : collection) { add(s); } } public void add(String s) { HashMap node = root; for (int i = 0; i ()); } node = node.get(character); } node.put(END_CHARACTER, new HashMap<>()); } public boolean contains(String s) { HashMap node = root; for (int i = 0; i < s.length(); i++) { Character character = s.charAt(i); if (node.containsKey(character)) { node = node.get(character); } else { return false; } } return node.containsKey(END_CHARACTER); } }
From whats-wrong-with-overridable-method-calls-in-constructors
Simply put, this is wrong because it unnecessarily opens up possibilities to MANY bugs. When the @Override is invoked, the state of the object may be inconsistent and/or incomplete.
This having in mind we will refactor the class, to add a private
%%CODEBLOCK_1%%
but we can do better.. let us take a look at
%%CODEBLOCK_2%%
If
Also if
%%CODEBLOCK_3%%
and call it
%%CODEBLOCK_4%%
But wait, we can do even better, as
%%CODEBLOCK_5%%
Finished ? No, we still can do better. As the passed String parameters won't be changed, let us make them
use interface types instead of the implementation
Putting altogether
```
public class Trie {
private final Map root = new HashMap<>();
private final Character END_CHARACTER = '$';
public Trie() {
}
public Trie(final String s) {
internalAdd(s);
}
public Trie(final Collection collection) {
for (String s : collection) {
internalAdd(s);
}
}
public void add(final String s) {
internalAdd(s);
}
private void internalAdd(final String s) {
Map node = root;
for (int i = 0; i ());
}
private void internalAdd(final String s, Map node) {
for (int i = 0; i ());
node = node.get(character);
}
}
public boolean contains(final String s) {
Map node = root;
for (int i = 0; i < s.length(); i++) {
if (node.isEmpty()) {
return false;
}
Character character = s.charAt(i);
if (node.containsKey(character)) {
node = node.get(character);
} else {
return false;
}
}
return node.contains
private HashMap root; at declaration will simplify your codepublic class Trie {
private HashMap root = new HashMap<>();
private final Character END_CHARACTER = '
From whats-wrong-with-overridable-method-calls-in-constructors
Simply put, this is wrong because it unnecessarily opens up possibilities to MANY bugs. When the @Override is invoked, the state of the object may be inconsistent and/or incomplete.
This having in mind we will refactor the class, to add a private internalAdd() method which we call from the constructor and the public add() methods
public class Trie {
private HashMap root = new HashMap<>();
private final Character END_CHARACTER = '
but we can do better.. let us take a look at internalAdd()
private void internalAdd(String s) {
HashMap node = root;
for (int i = 0; i ());
}
node = node.get(character);
}
node.put(END_CHARACTER, new HashMap<>());
}
If node.isEmpty() we won't need to check if (!node.containsKey(character)) anymore.
Also if (!node.containsKey(character)) evaluates one time to true, we won't need to check this anymore. Let us add a new method:
private void internalAdd(String s, HashMap node) {
for (int i = 0; i ());
node = node.get(character);
}
}
and call it
private void internalAdd(String s) {
HashMap node = root;
for (int i = 0; i ());
}
But wait, we can do even better, as node.isEmpty() should also be used in the contains() method
public boolean contains(String s) {
HashMap node = root;
for (int i = 0; i < s.length(); i++) {
if(node.isEmpty()){
return false;
}
Character character = s.charAt(i);
if (node.containsKey(character)) {
node = node.get(character);
} else {
return false;
}
}
return node.containsKey(END_CHARACTER);
}
Finished ? No, we still can do better. As the passed String parameters won't be changed, let us make them final the same is true for the root field. Also as janos has answered
use interface types instead of the implementation
Putting altogether
```
public class Trie {
private final Map root = new HashMap<>();
private final Character END_CHARACTER = '$';
public Trie() {
}
public Trie(final String s) {
internalAdd(s);
}
public Trie(final Collection collection) {
for (String s : collection) {
internalAdd(s);
}
}
public void add(final String s) {
internalAdd(s);
}
private void internalAdd(final String s) {
Map node = root;
for (int i = 0; i ());
}
private void internalAdd(final String s, Map node) {
for (int i = 0; i ());
node = node.get(character);
}
}
public boolean contains(final String s) {
Map node = root;
for (int i = 0; i < s.length(); i++) {
if (node.isEmpty()) {
return false;
}
Character character = s.charAt(i);
if (node.containsKey(character)) {
node = node.get(character);
} else {
return false;
}
}
return node.contains;
public Trie() {}
public Trie(String s) {
add(s);
}
public Trie(Collection collection) {
for (String s : collection) {
add(s);
}
}
public void add(String s) {
HashMap node = root;
for (int i = 0; i ());
}
node = node.get(character);
}
node.put(END_CHARACTER, new HashMap<>());
}
public boolean contains(String s) {
HashMap node = root;
for (int i = 0; i < s.length(); i++) {
Character character = s.charAt(i);
if (node.containsKey(character)) {
node = node.get(character);
} else {
return false;
}
}
return node.containsKey(END_CHARACTER);
}
}
From whats-wrong-with-overridable-method-calls-in-constructors
Simply put, this is wrong because it unnecessarily opens up possibilities to MANY bugs. When the @Override is invoked, the state of the object may be inconsistent and/or incomplete.
This having in mind we will refactor the class, to add a private internalAdd() method which we call from the constructor and the public add() methods
%%CODEBLOCK_1%%
but we can do better.. let us take a look at internalAdd()
%%CODEBLOCK_2%%
If node.isEmpty() we won't need to check if (!node.containsKey(character)) anymore.
Also if (!node.containsKey(character)) evaluates one time to true, we won't need to check this anymore. Let us add a new method:
%%CODEBLOCK_3%%
and call it
%%CODEBLOCK_4%%
But wait, we can do even better, as node.isEmpty() should also be used in the contains() method
%%CODEBLOCK_5%%
Finished ? No, we still can do better. As the passed String parameters won't be changed, let us make them final the same is true for the root field. Also as janos has answered
use interface types instead of the implementation
Putting altogether
```
public class Trie {
private final Map root = new HashMap<>();
private final Character END_CHARACTER = '$';
public Trie() {
}
public Trie(final String s) {
internalAdd(s);
}
public Trie(final Collection collection) {
for (String s : collection) {
internalAdd(s);
}
}
public void add(final String s) {
internalAdd(s);
}
private void internalAdd(final String s) {
Map node = root;
for (int i = 0; i ());
}
private void internalAdd(final String s, Map node) {
for (int i = 0; i ());
node = node.get(character);
}
}
public boolean contains(final String s) {
Map node = root;
for (int i = 0; i < s.length(); i++) {
if (node.isEmpty()) {
return false;
}
Character character = s.charAt(i);
if (node.containsKey(character)) {
node = node.get(character);
} else {
return false;
}
}
return node.contains;
public Trie() {}
public Trie(String s) {
internalAdd(s);
}
public Trie(Collection collection) {
for (String s : collection) {
internalAdd(s);
}
}
public void add(String s) {
internalAdd(s);
}
private void internalAdd(String s) {
HashMap node = root;
for (int i = 0; i ());
}
node = node.get(character);
}
node.put(END_CHARACTER, new HashMap<>());
}
public boolean contains(String s) {
HashMap node = root;
for (int i = 0; i < s.length(); i++) {
Character character = s.charAt(i);
if (node.containsKey(character)) {
node = node.get(character);
} else {
return false;
}
}
return node.containsKey(END_CHARACTER);
}
}but we can do better.. let us take a look at
internalAdd() %%CODEBLOCK_2%%
If
node.isEmpty() we won't need to check if (!node.containsKey(character)) anymore.Also if
(!node.containsKey(character)) evaluates one time to true, we won't need to check this anymore. Let us add a new method: %%CODEBLOCK_3%%
and call it
%%CODEBLOCK_4%%
But wait, we can do even better, as
node.isEmpty() should also be used in the contains() method %%CODEBLOCK_5%%
Finished ? No, we still can do better. As the passed String parameters won't be changed, let us make them
final the same is true for the root field. Also as janos has answereduse interface types instead of the implementation
Putting altogether
```
public class Trie {
private final Map root = new HashMap<>();
private final Character END_CHARACTER = '$';
public Trie() {
}
public Trie(final String s) {
internalAdd(s);
}
public Trie(final Collection collection) {
for (String s : collection) {
internalAdd(s);
}
}
public void add(final String s) {
internalAdd(s);
}
private void internalAdd(final String s) {
Map node = root;
for (int i = 0; i ());
}
private void internalAdd(final String s, Map node) {
for (int i = 0; i ());
node = node.get(character);
}
}
public boolean contains(final String s) {
Map node = root;
for (int i = 0; i < s.length(); i++) {
if (node.isEmpty()) {
return false;
}
Character character = s.charAt(i);
if (node.containsKey(character)) {
node = node.get(character);
} else {
return false;
}
}
return node.contains; public Trie() {} public Trie(String s) { add(s); } public Trie(Collection collection) { for (String s : collection) { add(s); } } public void add(String s) { HashMap node = root; for (int i = 0; i ()); } node = node.get(character); } node.put(END_CHARACTER, new HashMap<>()); } public boolean contains(String s) { HashMap node = root; for (int i = 0; i < s.length(); i++) { Character character = s.charAt(i); if (node.containsKey(character)) { node = node.get(character); } else { return false; } } return node.containsKey(END_CHARACTER); } }
From whats-wrong-with-overridable-method-calls-in-constructors
Simply put, this is wrong because it unnecessarily opens up possibilities to MANY bugs. When the @Override is invoked, the state of the object may be inconsistent and/or incomplete.
This having in mind we will refactor the class, to add a private
internalAdd() method which we call from the constructor and the public add() methods%%CODEBLOCK_1%%
but we can do better.. let us take a look at
internalAdd() %%CODEBLOCK_2%%
If
node.isEmpty() we won't need to check if (!node.containsKey(character)) anymore.Also if
(!node.containsKey(character)) evaluates one time to true, we won't need to check this anymore. Let us add a new method: %%CODEBLOCK_3%%
and call it
%%CODEBLOCK_4%%
But wait, we can do even better, as
node.isEmpty() should also be used in the contains() method %%CODEBLOCK_5%%
Finished ? No, we still can do better. As the passed String parameters won't be changed, let us make them
final the same is true for the root field. Also as janos has answereduse interface types instead of the implementation
Putting altogether
```
public class Trie {
private final Map root = new HashMap<>();
private final Character END_CHARACTER = '$';
public Trie() {
}
public Trie(final String s) {
internalAdd(s);
}
public Trie(final Collection collection) {
for (String s : collection) {
internalAdd(s);
}
}
public void add(final String s) {
internalAdd(s);
}
private void internalAdd(final String s) {
Map node = root;
for (int i = 0; i ());
}
private void internalAdd(final String s, Map node) {
for (int i = 0; i ());
node = node.get(character);
}
}
public boolean contains(final String s) {
Map node = root;
for (int i = 0; i < s.length(); i++) {
if (node.isEmpty()) {
return false;
}
Character character = s.charAt(i);
if (node.containsKey(character)) {
node = node.get(character);
} else {
return false;
}
}
return node.contains
Code Snippets
public class Trie {
private HashMap<Character, HashMap> root = new HashMap<>();
private final Character END_CHARACTER = '$';
public Trie() {}
public Trie(String s) {
add(s);
}
public Trie(Collection<String> collection) {
for (String s : collection) {
add(s);
}
}
public void add(String s) {
HashMap<Character, HashMap> node = root;
for (int i = 0; i < s.length(); i++) {
Character character = s.charAt(i);
if (!node.containsKey(character)) {
node.put(character, new HashMap<Character, HashMap>());
}
node = node.get(character);
}
node.put(END_CHARACTER, new HashMap<>());
}
public boolean contains(String s) {
HashMap<Character, HashMap> node = root;
for (int i = 0; i < s.length(); i++) {
Character character = s.charAt(i);
if (node.containsKey(character)) {
node = node.get(character);
} else {
return false;
}
}
return node.containsKey(END_CHARACTER);
}
}public class Trie {
private HashMap<Character, HashMap> root = new HashMap<>();
private final Character END_CHARACTER = '$';
public Trie() {}
public Trie(String s) {
internalAdd(s);
}
public Trie(Collection<String> collection) {
for (String s : collection) {
internalAdd(s);
}
}
public void add(String s) {
internalAdd(s);
}
private void internalAdd(String s) {
HashMap<Character, HashMap> node = root;
for (int i = 0; i < s.length(); i++) {
Character character = s.charAt(i);
if (!node.containsKey(character)) {
node.put(character, new HashMap<Character, HashMap>());
}
node = node.get(character);
}
node.put(END_CHARACTER, new HashMap<>());
}
public boolean contains(String s) {
HashMap<Character, HashMap> node = root;
for (int i = 0; i < s.length(); i++) {
Character character = s.charAt(i);
if (node.containsKey(character)) {
node = node.get(character);
} else {
return false;
}
}
return node.containsKey(END_CHARACTER);
}
}private void internalAdd(String s) {
HashMap<Character, HashMap> node = root;
for (int i = 0; i < s.length(); i++) {
Character character = s.charAt(i);
if (!node.containsKey(character)) {
node.put(character, new HashMap<Character, HashMap>());
}
node = node.get(character);
}
node.put(END_CHARACTER, new HashMap<>());
}private void internalAdd(String s, HashMap<Character, HashMap> node) {
for (int i = 0; i < s.length(); i++) {
Character character = s.charAt(i);
node.put(character, new HashMap<>());
node = node.get(character);
}
}private void internalAdd(String s) {
HashMap<Character, HashMap> node = root;
for (int i = 0; i < s.length(); i++) {
Character character = s.charAt(i);
if (node.isEmpty() || !node.containsKey(character)) {
internalAdd(s.substring(i), node);
break;
}
node = node.get(character);
}
node.put(END_CHARACTER, new HashMap<>());
}Context
StackExchange Code Review Q#59398, answer score: 7
Revisions (0)
No revisions yet.