创建一个开放的哈希表
Create an Open Hashtable
我是新手,现在我正在为大学编写代码。我想创建一个开放的哈希表,我写了这段代码:
public class AuDOpenHashTable extends AuDHashTable {
private LinkedList<Contact>[] table;
public AuDOpenHashTable(int capacity) {
super(capacity);
this.table = new LinkedList[capacity];
}
@Override
public void insert(Contact c) {
int position = hash(c.email);
if (table[position] == null) {
table[position] = new LinkedList<>();
}
table[position].add(c);
}
@Override
public void remove(Contact c) throws NoSuchElementException{
int position = hash(c.email);
if(table[position] != null){
table[position].remove();
}
else{
throw new NoSuchElementException();
}
}
@Override
public Contact getContact(String email)throws NoSuchElementException{
int position = hash(email);
table[position].getContact(email);
if(table[position] != null){
return table[position].get(position);
}
else{
throw new NoSuchElementException();
}
}
}
public abstract class AuDHashTable {
protected int capacity;
public AuDHashTable(int capacity){
this.capacity = capacity;
}
public abstract void insert(Contact c);
public abstract void remove(Contact c);
public abstract Contact getContact(String email);
protected int hash(String s){
int hash = 0;
for(int i = 0; i < s.length(); i++){
hash += s.charAt(i);
}
hash = hash % capacity;
return hash;
}
public static void main(String[] args) {
AuDClosedHashTable hashtabelle = new AuDClosedHashTable(3);
Contact eins = new Contact("hans.peter@web.de");
Contact zwei = new Contact("selina.meier@gmail.com");
Contact drei = new Contact("alexander.bauer@gmx.de");
hashtabelle.insert(eins);
hashtabelle.insert(zwei);
hashtabelle.insert(drei);
System.out.println(hashtabelle.isFull());
System.out.println(hashtabelle.getIndexOf("hans.peter@web.de"));
System.out.println(hashtabelle.getIndexOf("selina.meier@gmail.com"));
System.out.println(hashtabelle.getIndexOf("alexander.bauer@gmx.de"));
hashtabelle.remove(drei);
System.out.println(hashtabelle.isFull());
System.out.println(hashtabelle.getContact("selina.meier@gmail.com"));
System.out.println(hashtabelle.getContact("hans.peter@web.de"));
System.out.println(hashtabelle.getContact("alexander.bauer@gmx.de"));
AuDOpenHashTable hashtabelle = new AuDOpenHashTable(3);
Contact eins = new Contact("hans.peter@web.de");
Contact zwei = new Contact("selina.meier@gmail.com");
Contact drei = new Contact("alexander.bauer@gmx.de");
hashtabelle.insert(eins);
hashtabelle.insert(zwei);
hashtabelle.insert(drei);
System.out.println(hashtabelle.getContact("selina.meier@gmail.com"));
hashtabelle.remove(zwei);
System.out.println(hashtabelle.getContact("selina.meier@gmail.com"));
}
}
因此,我的问题出在 "getContact()" 方法中。如果我想在某个位置显示一个帐户,并且它是该位置的唯一帐户,那么一切正常。但是,如果要显示一个头尾不同的账户,所以有两个账户,它只给我一个账户(大部分不是正确的)。对于这些示例,代码运行良好,但如果我决定选择其他名称,有时它也不起作用。但为了不让事情变得复杂,我想听听您关于如何改进 "getContact" 方法的建议。预先感谢。
哈希函数会告诉您一个项目可以在哪个桶中,但您仍然需要检查桶中的所有项目是否相等。 getContact
应该遍历 LinkedList 并检查每个联系人的电子邮件,然后只 return 具有匹配电子邮件的联系人。 remove
方法相同。
不同的键可以有相同的哈希码。这通常是在插入时检测到的,在这种情况下,通常会有重新散列,一些算法会产生另一个散列码,这会导致另一个可能是免费的代码。如果不是免费的,它会再次重新散列。如果这种情况持续很多,那么 table 可能被分配给小的,应该使用更大的 table。
检索信息时,应将索引处的数据与搜索到的关键字进行比较。如果不匹配,则重新散列(与 insert 相同的算法)并重试。直到您找到它或在一个空索引中结束,在这种情况下,密钥不存在。
我是新手,现在我正在为大学编写代码。我想创建一个开放的哈希表,我写了这段代码:
public class AuDOpenHashTable extends AuDHashTable {
private LinkedList<Contact>[] table;
public AuDOpenHashTable(int capacity) {
super(capacity);
this.table = new LinkedList[capacity];
}
@Override
public void insert(Contact c) {
int position = hash(c.email);
if (table[position] == null) {
table[position] = new LinkedList<>();
}
table[position].add(c);
}
@Override
public void remove(Contact c) throws NoSuchElementException{
int position = hash(c.email);
if(table[position] != null){
table[position].remove();
}
else{
throw new NoSuchElementException();
}
}
@Override
public Contact getContact(String email)throws NoSuchElementException{
int position = hash(email);
table[position].getContact(email);
if(table[position] != null){
return table[position].get(position);
}
else{
throw new NoSuchElementException();
}
}
}
public abstract class AuDHashTable {
protected int capacity;
public AuDHashTable(int capacity){
this.capacity = capacity;
}
public abstract void insert(Contact c);
public abstract void remove(Contact c);
public abstract Contact getContact(String email);
protected int hash(String s){
int hash = 0;
for(int i = 0; i < s.length(); i++){
hash += s.charAt(i);
}
hash = hash % capacity;
return hash;
}
public static void main(String[] args) {
AuDClosedHashTable hashtabelle = new AuDClosedHashTable(3);
Contact eins = new Contact("hans.peter@web.de");
Contact zwei = new Contact("selina.meier@gmail.com");
Contact drei = new Contact("alexander.bauer@gmx.de");
hashtabelle.insert(eins);
hashtabelle.insert(zwei);
hashtabelle.insert(drei);
System.out.println(hashtabelle.isFull());
System.out.println(hashtabelle.getIndexOf("hans.peter@web.de"));
System.out.println(hashtabelle.getIndexOf("selina.meier@gmail.com"));
System.out.println(hashtabelle.getIndexOf("alexander.bauer@gmx.de"));
hashtabelle.remove(drei);
System.out.println(hashtabelle.isFull());
System.out.println(hashtabelle.getContact("selina.meier@gmail.com"));
System.out.println(hashtabelle.getContact("hans.peter@web.de"));
System.out.println(hashtabelle.getContact("alexander.bauer@gmx.de"));
AuDOpenHashTable hashtabelle = new AuDOpenHashTable(3);
Contact eins = new Contact("hans.peter@web.de");
Contact zwei = new Contact("selina.meier@gmail.com");
Contact drei = new Contact("alexander.bauer@gmx.de");
hashtabelle.insert(eins);
hashtabelle.insert(zwei);
hashtabelle.insert(drei);
System.out.println(hashtabelle.getContact("selina.meier@gmail.com"));
hashtabelle.remove(zwei);
System.out.println(hashtabelle.getContact("selina.meier@gmail.com"));
}
}
因此,我的问题出在 "getContact()" 方法中。如果我想在某个位置显示一个帐户,并且它是该位置的唯一帐户,那么一切正常。但是,如果要显示一个头尾不同的账户,所以有两个账户,它只给我一个账户(大部分不是正确的)。对于这些示例,代码运行良好,但如果我决定选择其他名称,有时它也不起作用。但为了不让事情变得复杂,我想听听您关于如何改进 "getContact" 方法的建议。预先感谢。
哈希函数会告诉您一个项目可以在哪个桶中,但您仍然需要检查桶中的所有项目是否相等。 getContact
应该遍历 LinkedList 并检查每个联系人的电子邮件,然后只 return 具有匹配电子邮件的联系人。 remove
方法相同。
不同的键可以有相同的哈希码。这通常是在插入时检测到的,在这种情况下,通常会有重新散列,一些算法会产生另一个散列码,这会导致另一个可能是免费的代码。如果不是免费的,它会再次重新散列。如果这种情况持续很多,那么 table 可能被分配给小的,应该使用更大的 table。
检索信息时,应将索引处的数据与搜索到的关键字进行比较。如果不匹配,则重新散列(与 insert 相同的算法)并重试。直到您找到它或在一个空索引中结束,在这种情况下,密钥不存在。