Вот что у меня получилось:
| Код |
public class HashMap
{
private final Entry[] entries;
private int size = 0;
public HashMap()
{
this(1024);
}
public HashMap(int size)
{
entries = new Entry[size];
}
public int getSize()
{
return size;
}
public boolean contains(String key)
{
Entry entry = entries[getIndex(key.hashCode())];
while(entry != null)
{
if(entry.key.equals(key))
return true;
entry = entry.next;
}
return false;
}
public int find(String key)
{
Entry entry = entries[getIndex(key.hashCode())];
while(entry != null)
{
if(entry.key.equals(key))
return entry.value;
entry = entry.next;
}
return -1;
}
public void put(String key, int value)
{
int idx = getIndex(key.hashCode());
Entry entry = entries[idx];
if(entry == null)
{
entries[idx] = new Entry(key, value);
size++;
}
else
{
while(entry != null)
{
if(entry.key.equals(key))
{
entry.value = value;
return;
}
if(entry.next == null)
{
entry.next = new Entry(key, value);
size++;
return;
}
entry = entry.next;
}
}
}
public int remove(String key)
{
int idx = getIndex(key.hashCode());
Entry entry = entries[idx];
if(entry == null)
{
return -1;
}
else
{
if(entry.key.equals(key))
{
entries[idx] = entry.next;
size--;
return entry.value;
}
Entry prev = entry;
entry = entry.next;
while(entry != null)
{
if(entry.key.equals(key))
{
prev.next = entry.next;
size--;
return entry.value;
}
prev = entry;
entry = entry.next;
}
return -1;
}
}
private int getIndex(int hash)
{
int i = hash % entries.length;
return i < 0 ? i + entries.length : i;
}
private class Entry
{
private Entry next;
private String key;
private int value;
public Entry(String key, int value)
{
this.key = key;
this.value = value;
}
}
}
|
| Код |
public class Table
{
public static final int Empty = 0;
public static final int Occupied = 1;
protected int m_capacity;// Table capacity.
protected int m_size;// Current number of elements the table holds.
protected TableEntry m_data[];// Elements.
// Returns true if key found, idx is then set to the index of
// element with that key in data array.
// If key is not found, returns false and set index to an empty
// location in the array (except array is full, then idx is set
// to the table capacity).
public boolean findKey(String key, int[] idx)
{
int empty = m_capacity;
for(int i = 0; i < m_capacity; ++i)
{
if((m_data[i].status == Empty) && (empty == m_capacity))
{
empty = i;
}
else if((m_data[i].status == Occupied) && (key.equals(m_data[i].key)))
{
idx[0] = i;
return true;
}
}
idx[0] = empty;
return false;
}
// Create a new table with given capacity.
public Table(int capacity)
{
m_capacity = capacity;
m_data = new TableEntry[m_capacity];
clear();
}
// Clears the table (erase all elements)
public void clear()
{
for(int i = 0; i < m_capacity; ++i)
{
m_data[i] = new TableEntry();
m_data[i].status = Empty;
m_data[i].key = null;
m_data[i].value = 0;
}
m_size = 0;
}
// Returns the number of elements in the table.
public int size()
{
return m_size;
}
// Returns true if table empty, otherwise false.
boolean isEmpty()
{
return m_size == 0;
}
// Insert an element into the table, if key already exists
// overwrite the value. Returns true if element found, otherwise flase.
public boolean insert(String key, int value)
{
int[] arr = {0};
int idx;
if(findKey(key, arr))
{
idx = arr[0];
// Key already in table, update value associated with key.
m_data[idx].value = value;
}
else
{
// Key not in table, add entry.
idx = arr[0];
if(idx < m_capacity)
{
m_data[idx].status = Occupied;
m_data[idx].key = key;
m_data[idx].value = value;
m_size++;
}
else
return false;// Table full.
}
return true;// Successful insertion!
}
// Delete element with key. Returns true if element found, otherwise false.
public boolean erase(String key)
{
int[] arr = {0};
if(findKey(key, arr))
{
int idx = arr[0];
m_data[idx].status = Empty;
m_data[idx].key = null;
m_data[idx].value = 0;
return true;
}
return false;
}
// Retrieve element with key (set value). Returns true if element found,
// otherwise false.
public boolean retrieve(String key, int[] value)
{
int[] arr = {0};
if(findKey(key, arr))
{
int idx = arr[0];
value[0] = m_data[idx].value;
return true;
}
return false;
}
// Collects n "first" elements in table into arrays key[] and value[]. Returns
// how many elements are collected (can be less than n). Note that the collected
// elements are not necessarily sorted.
public int collect(int n, String key[], int value[])
{
int collected = 0;
for(int idx = 0; idx < m_capacity; ++idx)
{
if(m_data[idx].status == Occupied)
{
if(collected < n)
{
key[collected] = m_data[idx].key;
value[collected] = m_data[idx].value;
collected++;
}
else
return collected;
}
}
return collected;
}
public static class TableEntry
{
int status;
String key;
int value;
}
}
|
| Код |
import java.io.*;
import java.nio.charset.Charset;
import java.util.Scanner;
public class SpellCheck
{
public static final double AVG_BYTES_PER_WORD = 5.0;
public static final int ITERATIONS = 10;
private static String fileEncoding;
public static void main(String[] args)
{
if(args.length < 1)
{
printUsage();
System.exit(1);
}
initCharset(args);
for(int i = 0; i < ITERATIONS; i++)
{
testHashMap(args[0]);
testTable(args[0]);
}
long time = System.currentTimeMillis();
for(int i = 0; i < ITERATIONS; i++)
testHashMap(args[0]);
time = System.currentTimeMillis() - time;
System.out.println("HashMap time = " + time / ITERATIONS + " ms");
time = System.currentTimeMillis();
for(int i = 0; i < ITERATIONS; i++)
testTable(args[0]);
time = System.currentTimeMillis() - time;
System.out.println("Table time = " + time / ITERATIONS + " ms");
}
private static void initCharset(String[] args)
{
if(args.length > 2 && Charset.isSupported(args[2]))
fileEncoding = args[2];
else
fileEncoding = Charset.defaultCharset().name();
}
private static void printUsage()
{
System.out.println("Usage: java SpellCheck <text_file> [<encoding>]");
}
private static HashMap testHashMap(String fileName)
{
try
{
File file = new File(fileName);
HashMap hashMap = new HashMap((int) (file.length() / AVG_BYTES_PER_WORD));
Scanner scanner = new Scanner(new FileInputStream(fileName), fileEncoding);
while(scanner.hasNext())
{
String s = scanner.next();
if(hashMap.contains(s))
{
hashMap.put(s, hashMap.find(s) + 1);
}
else
{
hashMap.put(s, 1);
}
}
scanner.close();
return hashMap;
}
catch(IOException e)
{
System.err.println("Error reading input file: " + e.getMessage());
System.exit(2);
return null;
}
}
private static Table testTable(String fileName)
{
try
{
File file = new File(fileName);
Table table = new Table((int) (file.length() / AVG_BYTES_PER_WORD));
Scanner scanner = new Scanner(new FileInputStream(fileName), fileEncoding);
int[] idx = new int[1];
while(scanner.hasNext())
{
String s = scanner.next();
if(table.findKey(s, idx))
{
table.insert(s, idx[0] + 1);
}
else
{
table.insert(s, 1);
}
}
scanner.close();
return table;
}
catch(IOException e)
{
System.err.println("Error reading input file: " + e.getMessage());
System.exit(2);
return null;
}
}
}
|
|
)
, мне совсем не понятно как можно протестировать и сравнить данные.
