Java 데이터 구조 --HashTable(지퍼법)
양방향 노드
/**
* Created by root on 16-3-6.
*/
public class Node<E> {
public E data;
public Node prev;
public Node next;
public Node(E target,Node prev,Node next){//
data=target;
this.prev=prev;
this.next=next;
}
public Node(){
this(null,null,null);
}
public Node(E target){
this(target,null,null);
}
}
양방향 체인 테이블은 데이터 단원을 저장하는 데 쓰인다
/**
* Created by root on 16-3-6.
*/
public class MyLinkedList<E> {
private Node beginMaker;
private Node endMaker;
private int size; //length
public boolean isEmpty(){
return beginMaker.next==endMaker;
}
public MyLinkedList() { //Constructor
beginMaker = new Node();
endMaker = new Node(null, beginMaker, null);// beginMaker endMaker
beginMaker.next=endMaker;
size = 0;
}
public MyLinkedList(int thatSize, E target) { //Constructor
this();
size = thatSize;
for (int i = 0; i < size; i++) {
this.add(target);
}
}
public void add(E target) {
Node node = new Node(target, endMaker.prev, endMaker);// 4
node.prev.next = node;
endMaker.prev = node;
size++;
}
public boolean contains(E target) {//
Node node = findNode(target);
if (node != null) {
return true;
} else {
return false;
}
}
public boolean remove(E target) { //delete
Node node = findNode(target);
if (node != null) {
node.prev.next = node.next;//
node.next.prev = node.prev;
size--;
return true;
}
return false;
}
private Node findNode(E target) {//
Node node1 = beginMaker.next;
Node node2 = endMaker.prev;
if(isEmpty())return null;
for (int i = 0; i <= size / 2; i++) {
if (node1.data.equals(target)) {
return node1;
} else if (node2.data.equals(target)) {
return node2;
} else {
node1 = node1.next;
node2 = node2.prev;
}
}
return null;
}
public Node getNode(int index) {// Index size/2
if (index >= size) {
throw new IndexOutOfBoundsException();
} else if (index < size / 2) {
Node node = beginMaker.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
Node node = endMaker.prev;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
}
HashTable List는 양방향 체인 테이블을 저장하여 십자 체인 테이블을 구성하는 데 사용됩니다.
/**
* Created by root on 16-3-6.
*/
public class HashTableList {
public static class hNode {
MyLinkedList data;
hNode prev;
hNode next;
public hNode(MyLinkedList list, hNode prev, hNode next) {
data = list;
this.prev = prev;
this.next = next;
}
}
public hNode beginMaker;
public hNode endMaker;
public int size;
public HashTableList() {
beginMaker = new hNode(null, null, null);
endMaker = new hNode(null, beginMaker, null);
size = 0;
}
public HashTableList(int size) {
this();
for (int i = 0; i < size; i++) {
this.add(new MyLinkedList());
}
}
public void add(MyLinkedList target) {
hNode node = new hNode(target, endMaker.prev, endMaker);
node.prev.next = node;
endMaker.prev = node;
size++;
}
public hNode gethNode(int index) {// Index size/2
if (index >= size) {
throw new IndexOutOfBoundsException();
} else if (index < size / 2) {
hNode node = beginMaker.next;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
} else {
hNode node = endMaker.prev;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
}
HashTable 추가 및 삭제 및 찾기
/**
* Created by root on 16-3-6.
*/
public class HashTable<E> {
HashTableList list;
int size;
public HashTable(int size) {
list = new HashTableList(size);
this.size = size;
}
public void insert(E target) {
int hashVal = myHash(target);
MyLinkedList myLinkedList = list.gethNode(hashVal).data;
if (!myLinkedList.contains(target)) {
myLinkedList.add(target);
}
}
public boolean remove(E target) {
int hashVal = myHash(target);
MyLinkedList myLinkedList = list.gethNode(hashVal).data;
return myLinkedList.remove(target);
}
public int myHash(E target) {
int hashVal = target.hashCode();
hashVal %= size;
if (hashVal < 0) {
hashVal += size;
}
return hashVal;
}
public int contains(E target) {
int hashVal = myHash(target);
MyLinkedList myLinkedList = list.gethNode(hashVal).data;
if (myLinkedList.contains(target)) {
return hashVal;
} else {
return -1;
}
}
}
테스트 클래스
/**
* Created by root on 16-3-6.
*/
public class Test {
public static void main(String[] args){
HashTable hashTable=new HashTable(11) ;
hashTable.insert(12);
hashTable.insert("sjkljg");
hashTable.insert(145);
System.out.println(hashTable.contains(12));
System.out.println(hashTable.contains(145));
System.out.println(hashTable.contains("sjkljg"));
hashTable.remove(12);
System.out.println(hashTable.contains(12));
}
}
결과 내보내기
1
2
9
-1
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.