배열, 링크, Hash
배열 과 링크 의 차이 점:
1. 배열 은 요 소 를 메모리 에 연속 으로 저장 합 니 다.
링크 에 있 는 요 소 는 메모리 에 순서대로 저장 되 는 것 이 아니 라 요소 에 존재 하 는 지침 을 통 해 연 결 됩 니 다.
2. 배열 은 반드시 고정된 길 이 를 미리 정의 해 야 하 며 데이터 의 동태 적 인 증감 상황 에 적응 하지 못 한다.데이터 가 증가 할 때 원래 정 의 된 요소 개 수 를 초과 할 수 있 습 니 다.데이터 가 줄 어 들 때 메모리 낭 비 를 초래한다.
링크 는 동태 적 으로 저장 분 배 를 하면 데이터 가 동태 적 으로 증가 하고 감소 하 는 상황 에 적응 할 수 있다.
3. (정적) 배열 은 스 택 에서 공간 을 분배 하고 프로그래머 에 게 편리 하고 빠 르 지만 자유도 가 적다.
링크 는 더미 에서 공간 을 분배 하고 자유도 가 높 지만 신청 관리 가 비교적 번거롭다.
배열 과 링크 는 데 이 터 를 저장 하 는 데 있어 서 도대체 어느 것 이 좋 고 어느 것 이 나 쁜 가?배열 과 링크 의 특성 에 따라 두 가지 상황 으로 나 누 어 토론 한다.
1. 데이터 조 회 를 할 때 배열 은 아래 표 시 를 통 해 배열 의 요 소 를 신속하게 방문 할 수 있 습 니 다.한편, 링크 는 첫 번 째 요소 부터 필요 한 요소 의 위 치 를 계속 찾 아야 한다. 분명히 배열 의 조회 효율 은 링크 보다 높 을 것 이다.
2. 요 소 를 추가 하거나 삭제 할 때 배열 에 요 소 를 추가 합 니 다. 대량의 요 소 를 이동 하고 메모리 에 요소 의 공간 을 비 운 다음 에 추가 할 요 소 를 그 안에 두 어야 합 니 다.마찬가지 로 하나의 요 소 를 삭제 하려 면 이동 하 는 요 소 를 채 우기 위해 대량의 요 소 를 이동 해 야 합 니 다.체인 테이블 은 원소 중의 바늘 만 바 꾸 면 원 소 를 증가 하거나 삭제 할 수 있다.
그러면 우 리 는 배열 의 빠 른 조회 장점 을 가지 고 링크 를 융합 시 켜 요 소 를 삭제 하 는 장점 을 신속하게 증가 시 킬 수 있 는 방법 이 있 을 까?HASH 가 부 르 면 나 오 려 고 합 니 다.
hash 란 쉽게 말 하면 해시 입 니 다. 입력 할 데 이 터 는 hash 함 수 를 통 해 key 값 을 얻 고 입력 한 데 이 터 는 배열 에서 key 값 으로 표 시 된 배열 단원 에 저 장 됩 니 다.
우 리 는 서로 다른 데이터 가 hash 함 수 를 통 해 같은 key 값 을 얻 는 것 을 발견 했다.이때 hash 충돌 이 생 겼 습 니 다.hash 충돌 을 해결 하 는 방식 은 두 가지 가 있 습 니 다.하 나 는 체인 식 이 고 지퍼 법 이 라 고도 합 니 다.체인 식 사상 은 충돌 이 발생 하 는 hash 주소 에서 체인 테이블 을 가리 키 며 같은 키 값 을 가 진 데 이 터 를 체인 테이블 에 저장 합 니 다.다른 하 나 는 공공 유출 구역 을 만 드 는 것 이다.충돌 이 발생 한 모든 데 이 터 를 공공 유출 구역 에 저장 하면 문 제 를 해결 할 수 있다.
어떻게 hash 의 동적 증가 공간의 효 과 를 실현 합 니까?이것 은 인자 에 담 는 것 과 밀접 한 관계 가 있다.인 자 를 채 웁 니 다 = 표 에 있 는 요소 의 개수 / 산 목록 의 길 이 를 채 웁 니 다.장 착 인자 가 일정한 값 a 에 이 르 렀 을 때, 우 리 는 배열 에 일정한 메모리 공간 을 증가 시 키 는 동시에 rehash.
다음은 두 가지 예시 로 이 해 를 깊이 있 게 한다.
예제 1: 링크 로 대기 열 을 실현 합 니 다.
노드 클래스
package cn.netjava.hash;
public class LinkNode {
// ： Object
public LinkNode(Object obj){
data=obj;
}
public Object data; //Object
public LinkNode next;//
// toString
public String toString(){
//System.out.println(data);
return (String)data;
}
// Object
public Object getData(){
return data;
}
// Onject
public Object Update(Object o){
data=o;
return o;
}
}
대기 열 클래스
package cn.netjava.hash;
public class LinkQueue {
public LinkNode front=null;//
public LinkNode last=null;//
public static void main(String args[]){
LinkQueue lq=new LinkQueue();
LinkNode lq1=new LinkNode(" 1");
LinkNode lq2=new LinkNode(" 2");
LinkNode lq3=new LinkNode(" 3");
LinkNode lq4=new LinkNode(" 4");
lq.InsertLinkNode(lq1);
lq.InsertLinkNode(lq2);
lq.InsertLinkNode(lq3);
lq.InsertLinkNode(lq4);
int count=lq.getLength();
System.out.println(" "+count);
for(int i=0;i<count;i++){
LinkNode ln = lq.getLinkNode(i);
System.out.println(" "+i+" "+ln.getData().toString());
}
lq.deleteLinkNode(2);
count=lq.getLength();
System.out.println(" "+lq.getLength());
for(int i=0;i<count;i++){
LinkNode ln = lq.getLinkNode(i);
System.out.println(" "+i+" "+ln.getData().toString());
}
lq.getLinkNode(1).Update(" ");
for(int i=0;i<count;i++){
LinkNode ln = lq.getLinkNode(i);
System.out.println(" "+i+" "+ln.getData().toString());
}
for(int i=0;i<200;i++){
LinkNode ln = new LinkNode(i);
lq.InsertLinkNode(ln);
}
System.out.println(" "+lq.getLength());
}
/**
*
* @param obj：
*/
public void InsertLinkNode(Object obj){
// ，
if(front==null){
front=new LinkNode(obj);
last=front;
}
// ，
else{
LinkNode next=new LinkNode(obj);
last.next=next;
last=next;
}
}
/**
*
* @param index
*/
public void insertIndexObj(int index,Object obj){
// ， ，
int total=getLength();
if(index>total||index<0)
throw new java.lang.RuntimeException(" ！");
LinkNode lNode=getLinkNode(index);
LinkNode linkNode=new LinkNode(obj);
lNode.insert(linkNode);
}
/**
*
* @param index：
*/
public void deleteLinkNode(int index){
// ， ，
int total=getLength();
if(index>total||index<0)
throw new java.lang.RuntimeException(" ！");
if(front!=null){
LinkNode n=front;
LinkNode m=front;
int count=0;
while(n!=null){
if(count==index){
if(n.equals(front)){
front=front.next;
}
else{
m.next=n.next;
}
}
m=n;
n=n.next;
count++;
}
}
}
/**
*
* @param lNode:
* @return：
*/
public LinkNode getLinkNode(int index){
if(front==null)
return null;
LinkNode l=front;
int count=0;
while(l!=null){
if(count==index)
return l;
count++;
l=l.next;
}
return null;
}
/**
*
* @return：
*/
public int getLength(){
if(front==null)
return 0;
LinkNode l=front;
int count=0;
while(l!=null){
count++;
l=l.next;
}
return count;
}
/**
*
* @param index：
* @param obj：
*/
public void UpdateLinkNode(int index,Object obj){
LinkNode lNode=getLinkNode(index);
lNode.Update(obj);
}
}
예제 2: QQ 번호 및 QQ 사용자 저장
QQ 사용자 클래스
package cn.netjava.hash;
public class QQUser {
public String userName;//
public String passWord;//
public String sex;//
public int age;//
public String getUserName() {
return userName;
}
public void setUserName(String userName) {
this.userName = userName;
}
public String getPassWord() {
return passWord;
}
public void setPassWord(String passWord) {
this.passWord = passWord;
}
public String getSex() {
return sex;
}
public void setSex(String sex) {
this.sex = sex;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
}
대기 열 클래스
package cn.netjava.hash;
public class LinkQueue {
public LinkNode front=null;//
public LinkNode last=null;//
/**
*
* @param index：
*/
public void deleteLinkNode(int index){
if(index<0||index>)
if(front!=null){
LinkNode n=front;
LinkNode m=front;
int count=0;
while(n!=null){
if(count==index){
if(n.equals(front)){
front=front.next;
}
else{
m.next=n.next;
}
}
m=n;
n=n.next;
count++;
}
}
}
/**
*
* @param lNode:
* @return：
*/
public LinkNode getLinkNode(int index){
if(front==null)
return null;
LinkNode l=front;
int count=0;
while(l!=null){
if(count==index)
return l;
count++;
l=l.next;
}
return null;
}
/**
*
* @return：
*/
public int getLength(){
if(front==null)
return 0;
LinkNode l=front;
int count=0;
while(l!=null){
count++;
l=l.next;
}
return count;
}
/**
*
* @param index：
* @param obj：
*/
public void UpdateLinkNode(int index,Object obj){
LinkNode lNode=getLinkNode(index);
lNode.Update(obj);
}
}QQ 노드 클래스
package cn.netjava.hash;
public class QQNode {
// ： QQ ，QQ
public QQNode(int qq,QQUser user){
this.qq=qq;
this.user=user;
}
public int qq;//QQ
public QQUser user;//QQ
public QQNode next;// QQ
public LinkQueue lq;//
public LinkQueue getLq() {
return lq;
}
public void setLq(LinkQueue lq) {
this.lq = lq;
}
public int getQq() {
return qq;
}
public void setQq(int qq) {
this.qq = qq;
}
public QQUser getUser() {
return user;
}
public void setUser(QQUser user) {
this.user = user;
}
public QQNode getNext() {
return next;
}
public void setNext(QQNode next) {
this.next = next;
}
}
Hash 방법 류
package cn.netjava.hash;
public class QQHash {
private QQNode[] table=new QQNode[100];
private float load=0.75F;//
private int count=0;
private int gain=100;
public static void main(String args[]){
QQHash qqHash=new QQHash();
QQUser user1=new QQUser();
user1.setUserName(" ");
user1.setPassWord("1");
user1.setAge(20);
user1.setSex(" ");
qqHash.put(1, user1);
QQUser user2=new QQUser();
user2.setUserName(" ");
user2.setPassWord("12");
user2.setAge(20);
user2.setSex(" ");
qqHash.put(2, user2);
QQUser user3=new QQUser();
user3.setUserName(" ");
user3.setPassWord("123");
user3.setAge(20);
user3.setSex(" ");
qqHash.put(3, user3);
QQUser user4=new QQUser();
user4.setUserName(" ");
user4.setPassWord("1234");
user4.setAge(20);
user4.setSex(" ");
qqHash.put(101, user4);
qqHash.returnQQNode();
user1=qqHash.get(1);
user2=qqHash.get(2);
user3=qqHash.get(3);
user4=qqHash.get(101);
QQNode[] table=qqHash.returnQQNode();
// System.out.println(" "+table.length);
qqHash.returnTabLen();
for(int i=0;i<table.length;i++){
if(table[i]!=null){
System.out.println(" Table["+i+"] "+table[i].getQq());
LinkQueue lq=table[i].getLq();
if(lq.getLength()>0){
System.out.println(" ");
for(int j=0;j<lq.getLength();j++)
System.out.println(" "+i+" "+((QQNode)lq.getLinkNode(i).getData()).getUser().getUserName());
}
}
}
}
/**
* QQ
* @param qq:QQ
* @param user：QQ
*/
public void put(int qq,QQUser user){
// table ,
// , reHash , ,
// !
float rate=(float)count/table.length;
if(rate>=load){
QQNode[] table1=new QQNode[table.length+gain];
for(int i=0;i<table.length;i++){
QQNode q=table[i];
int qqnum=q.getQq();
QQUser u=q.getUser();
int qqhash=hashQQ(qqnum);
q.setQq(qqnum);
q.setUser(user);
table1[qqhash]=q;
}
table=table1;
}
System.out.println("table ："+table.length);
// hash
boolean judge=exist(qq);
System.out.println(" "+judge);
int index=hashQQ(qq);
System.out.println("hash "+index);
if(judge){// hash ， qq hash
QQNode q=new QQNode(qq,user);
q.setQq(qq);
q.setUser(user);
table[index]=q;
count++;
}
else{// hash
QQNode q=new QQNode(qq,user);
q.setQq(qq);
q.setUser(user);
System.out.println(" "+q.getQq()+" "+q.getUser());
LinkQueue lq=q.getLq();
lq.InsertLinkNode(q);
for(int i=0;i<lq.getLength();i++)
System.out.println("======"+((QQNode)lq.getLinkNode(i).getData()).getQq());
if(lq.getLength()==0){
table[index].setNext(q);
}
}
}
/**
* QQ QQ
* @param qq：QQ
* @return:QQ
*/
public QQUser get(int qq){
int index=hashQQ(qq);
QQNode q=table[index];
System.out.println(" "+q.getQq());
// , , ,
if(q.next==null)
return q.getUser();
LinkQueue lq=q.getLq();
for(int i=0;i<lq.getLength();i++){
QQNode aa=(QQNode)lq.getLinkNode(i).data;
int qqq=aa.getQq();
if(qqq==qq)
System.out.println(" ！");
return aa.getUser();
}
return null;
}
// QQ has , has
private int hashQQ(int qq){
return qq%table.length;
}
// hash
private boolean exist(int qq){
int qqhash=hashQQ(qq);
if(table[qqhash]!=null)
return false;
return true;
}
//
private QQNode[] returnQQNode(){
System.out.println(" "+count);
return this.table;
}
//
private int returnTabLen(){
return this.count;
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
