Implementation of hashcode for a more efficient String hash

Unicode uses 16 bits per character, allowing for 2^16 possibilities. A String with 2147483647 (Integer.MAX_VALUE) characters has 2^34359738352 possibilities. What a large number! Thus, it is of no doubt that the hashCode method of the String class is less efficient than that of Long, since the number of all unique possibilities of a String is by far larger than Long's.

However, regarding Strings that match certain patterns, the number of unique possibilities is much smaller. For example, the number of English vocabularies with length below is lower than 2^64, the number of a Long's possibilities. For a class with a single non-static field "long test", the hashcode is simply "31 + (int) (test ^ (test >>> 32));", which is much more efficient than that of String, "s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]".

The Java code below is an implementation of a more efficient hashcode for "English vocabularies with length below 12." (The first character can be upper-cased, and other characters should be lower-cased. No whitespace, hyphens, or other character are allowed.)

package com.packa9e;

import java.util.HashMap;

public class Vocabulary  {

 private final StringBuilder vocabulary;
 private long[] digits = new long[12];
 
 public Vocabulary(String vocabulary){
  this.vocabulary = new StringBuilder(vocabulary);
  if (hasInputError())
   new Exception("Not a valid vocabulary").printStackTrace();
 }
 
 private boolean hasInputError(){
  if (vocabulary.length() > 12 )
   return true;
  
  if (vocabulary.charAt(0) >= 65 && vocabulary.charAt(0) <= 90) //A-Z
   digits[0] = vocabulary.charAt(0) - 38; // A - 27 ... Z - 52 
  else if (vocabulary.charAt(0) >= 97 && vocabulary.charAt(0) <= 122)
   digits[0] = vocabulary.charAt(0) - 96; //a - 1 .. z - 26
  else
   return true;
   
  for (int i = 1 ; i < vocabulary.length(); i++){
   if (vocabulary.charAt(i) >= 97 && vocabulary.charAt(i) <= 122)
    digits[i] = vocabulary.charAt(0) - 96; //a - 1 ... z - 26
   else
    return true;
  }
  return false;
 }
 
 @Override
 public int hashCode() {
  Long longValue = digits[0] << 55;
  for (int i = 1 ; i < vocabulary.length(); i++){
   longValue += digits[i] << (5 * (11 - i));
  }
  return longValue.hashCode();
 }

 @Override
 public boolean equals(Object obj) {
  if (this == obj)
   return true;
  if (obj == null)
   return false;
  if (getClass() != obj.getClass())
   return false;
  Vocabulary other = (Vocabulary) obj;
  if (vocabulary == null) {
   if (other.vocabulary != null)
    return false;
  } else if (!vocabulary.toString().equals(other.vocabulary.toString()))
   return false;
  return true;
 }
 
 public static void main(String[] args) {
  HashMap hashMap = new HashMap();
  Vocabulary v1 = new Vocabulary("test");
  hashMap.put(v1, "reg4te");
  Vocabulary v2 = new Vocabulary("test");
  System.out.println(hashMap.get(v2));
 }
}

Implementation of a Card Shuffling Algorithm in Java

About 15 months ago, I had an interview in a company around  Da Qiao Tou station. The supervisor asked me about how to efficiently shuffle cards by C#, and I didn't quickly figured out a good answer. Finally, he said that the most efficient card Shuffling algorithm is to do thousands or a millions times of swap of two randomly chosen cards. I didn't think clearly and assumed that his view is correct. Now I realized that the algorithm he said is not efficient enough, much less the most efficient algorithm.

The following is a Java implementation of a card shuffling algorithm which took just a few thousands of simple addition by 1 or subtraction by one. The generated deck of card is completely random provided that random numbers generated with java.util.Random and its methods are random. You can copy the codes and configure them on your own.



Card.java

package com.cardshuffler;

public class Card {
 public enum Suit{
  Club, Diamond, Heart, Spade, 
 }
 
 public final Suit suit;
 public final int number; //J is represented by 11, and Q by 12, K by 13
 public Card(Suit suit, int number) {
  this.suit = suit;
  this.number = number;
 }
 
 @Override
 public String toString(){
  return suit + "-" + number;
 }
}

CardShuffler.java

package com.cardshuffler;

import java.util.*;
import com.cardshuffler.Card.Suit;

public class CardShuffler {

 private Random random;
 private ArrayList cards;

 public CardShuffler() {
  cards = new ArrayList();
  random = new Random();
 }

 public void shuffle() {
  final int cardNum = 52;
  boolean[] selected = new boolean[cardNum];
  for (int i = cardNum; i >= 1; i--) {
   int count = -1;
   int randomNumber = random.nextInt(i) + 1;
   for (int j = 0; j < randomNumber ; j++){
    count++;
    while (selected[count])
     count++;
   }
   selected[count] = true;
   cards.add(getCardByNumber(count));
  }
 }

 /**
  * the input number should be between 0 to 51
  * @param number
  * @return
  */
 private Card getCardByNumber(int number) {
  Suit suit = null;
  int a = number / 13;
  switch (a) {
  case 0:
   suit = Suit.Club;
   break;
  case 1:
   suit = Suit.Diamond;
   break;
  case 2:
   suit = Suit.Heart;
   break;
  case 3:
   suit = Suit.Spade;
   break;
  }
  
  return new Card(suit, number%13 + 1);
 }

 public ArrayList getCards() {
  return cards;
 }

 public static void main(String[] args) {
  CardShuffler shuffler = new CardShuffler();
  shuffler.shuffle();
  List shuffledCards = shuffler.getCards();
  
  System.out.println("The resulting shuffled cards are:");
  for (Card card : shuffledCards)
   System.out.println(card);
  
 }
}

A Java Code Searcher

Recently, in my computer, I noticed by accident that the "File Search" functionality in my Eclipse Helios is broken, and I don't know why. Whenever I press Ctrl + H, click the File Search tab, input a string I want to search, and click the search button, the result is always "0 matches in working space." After searching the Internet a while to look forward a solution, I still haven't found one. Thus, I wrote a simple but useful executable jar application for searching codes inside a project. The following are the codes and a tutorial about how to it.

Step 1: Download the CodeSearcher.jar from https://sites.google.com/site/moderntone/CodeSearcher.jar?attredirects=0&d=1

Step 2: Copy the CodeSearcher.jar to the project folder



Step 3: Click the jar file, type the string you want to search in your project codes, and found lines are immediately shown in the JScrollPane. You can also press the Enter key to refresh the JScrollPane.




You can also configure the CodeSearcher.java on your own and compile a new code searcher. For example, to search codes in a C# project or other types to files, you can assign "new String[] {".cs", ".log"};" instead of "new String[] {".java"};" to the static final String[] extensions. If you want to search the whole workspace, copy the CodeSearch.jar to your workspace folder.

CodeSearcher.java

package com.codesearcher;

import java.io.File;
import java.util.ArrayList;

public class CodeSearcher {
 
 private static final String[] extensions = new String[] {".java"};
 private String fileOrDirectoryPath;
 private ArrayList files;
 
 public CodeSearcher(String fileOrDirectoryPath) {
  this.fileOrDirectoryPath = fileOrDirectoryPath;
 }

 public CodeSearcher(){
  String path = getClass().getProtectionDomain().getCodeSource().getLocation().getPath();
  this.fileOrDirectoryPath = path.substring(1, path.lastIndexOf("/"));
  files = getAllFiles();
 }
 
 public ArrayList getAllFiles(){
  if (files == null){
   ArrayList files = new ArrayList();
   File directoryOrFile = new File(fileOrDirectoryPath);
   if (!directoryOrFile.exists())
    return files;
   
   File[] listOfFiles = directoryOrFile.listFiles(); 
   if (listOfFiles == null){
    boolean fitsExtension = false;
    for (String extension : extensions){
     if (directoryOrFile.getAbsolutePath().endsWith(extension))
      fitsExtension = true;
    }
    if (fitsExtension) files.add(directoryOrFile);
    return files;
   }
   else {
    for (File file : listOfFiles){
     CodeSearcher searcher = new CodeSearcher(file.getAbsolutePath());
     files.addAll(searcher.getAllFiles());
    }
    return files;
   }
  }
  return files;
  
 }

 public ArrayList searchLines(ArrayList allLines, String target){
  ArrayList linesFound = new ArrayList();
  String targetToLowerCase = target.toLowerCase();
  
  for (String line : allLines){
   int indexOfColonPlus1 = line.indexOf(":") + 1;
   String lineToLowerCase = line.substring(indexOfColonPlus1).toLowerCase();
   if (lineToLowerCase.contains(targetToLowerCase))
    linesFound.add(line);
  }
  return linesFound;
 }
}

Main.java

package com.codesearcher;

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.io.*;
import java.util.ArrayList;
import javax.swing.border.*;

public class Main extends JFrame {

 private static final long serialVersionUID = 1L;
 private JPanel contentPane;
 private JTextField textField;
 private JTextArea textArea;
 
 private static ArrayList allFiles;
 private static ArrayList allLines;
 private static CodeSearcher codeSearcher;
 
 private static Main frame;
 public static void main(String[] args) {
  
  EventQueue.invokeLater(new Runnable() {
   public void run() {
    try {
     frame = new Main();
     frame.setVisible(true);
    } catch (Exception e) {
     e.printStackTrace();
    }
   }
  });
  
  codeSearcher = new CodeSearcher();
  allFiles = codeSearcher.getAllFiles();
  setAllLines(allFiles);
 }


 public Main() {
  setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
  setBounds(300, 100, 700, 500);
  setResizable(false);
  setTitle("Code Searcher");
  contentPane = new JPanel();
  contentPane.setBorder(new EmptyBorder(5, 5, 5, 5));
  contentPane.setLayout(null);
  setContentPane(contentPane);
  
  textField = new JTextField();
  textField.setFont(new Font("Tahoma", Font.PLAIN, 15));
  textField.setBounds(259, 60, 180, 27);
  textField.addKeyListener(new KeyListener() {
   
   @Override
   public void keyTyped(KeyEvent arg0) {
   }
   
   @Override
   public void keyReleased(KeyEvent arg0) {
   }
   
   @Override
   public void keyPressed(KeyEvent arg0) {
    performAction();
   }
  });
  contentPane.add(textField);
  
  JLabel lblInputTextTo = new JLabel("Input text to search codes");
  lblInputTextTo.setFont(new Font("Century", Font.PLAIN, 18));
  lblInputTextTo.setForeground(Color.BLUE);
  lblInputTextTo.setBounds(242, 23, 220, 27);
  contentPane.add(lblInputTextTo);
  
  textArea = new JTextArea();
  textArea.setFont(new Font("Microsoft New Tai Lue", Font.PLAIN, 12));
  textArea.setEditable(false);
  textArea.setBorder(new EtchedBorder(EtchedBorder.RAISED, Color.MAGENTA, null));
  textArea.setBounds(48, 110, getWidth() - 100, 300);
  JScrollPane scrollPane = new JScrollPane(textArea,  
    JScrollPane.VERTICAL_SCROLLBAR_AS_NEEDED, JScrollPane.HORIZONTAL_SCROLLBAR_AS_NEEDED);
  scrollPane.setBounds(48, 110, 600, 300);

  contentPane.add(scrollPane);
  
  JButton btnClear = new JButton("Clear");
  btnClear.addActionListener(new ActionListener() {
   public void actionPerformed(ActionEvent arg0) {
    textArea.setText("");
   }
  });
  btnClear.setBounds(317, 424, 74, 23);
  contentPane.add(btnClear);
  
  JButton btnSearch = new JButton("Search");
  btnSearch.addActionListener(new ActionListener() {
   public void actionPerformed(ActionEvent arg0) {
    performAction();
   }
  });
  btnSearch.setBounds(459, 61, 81, 25);
  contentPane.add(btnSearch);
 }
 
 private static void setAllLines(ArrayList files){
  if (allLines != null)
   return;
  
  allLines = new ArrayList();
  for (File javaFile : files){
   try {
    FileReader read = new FileReader(javaFile);
    BufferedReader reader = new BufferedReader(read);
    String line; 
    int count = 1;
    while ((line = reader.readLine()) != null) {
     line = javaFile.getName() + " " + count + " : " + line;
     allLines.add(line);
     count++;
    }
   } catch (FileNotFoundException e) {
    e.printStackTrace();
   } catch (IOException e) {
    e.printStackTrace();
   }
  }
  
 }
 
 private void performAction(){
  ArrayList linesFound = 
   codeSearcher.searchLines(allLines, textField.getText());
  StringBuilder builder = new StringBuilder();
  for (String foundLine : linesFound){
   builder.append(foundLine + "\n");
  }
  textArea.setText(builder.toString());
 }
}