反向DNS查找是使用internet IP地址查找域名。例如，如果在浏览器中键入74.125.200.106，它会自动重定向到谷歌。在里面 如何实现反向DNS查找缓存？以下是缓存所需的操作：
null
- 在缓存中添加IP地址到URL映射。
- 查找给定IP地址的URL。
一个解决方案是使用 散列 . 在这篇文章中，一个 崔 讨论了基于该方法的解决方案。基于Trie的解决方案的一个优点是，对于Trie，最坏情况的上界是O（1），对于散列，最好的平均情况时间复杂度是O（1）。此外，通过Trie，我们可以实现前缀搜索（查找IP地址公共前缀的所有URL）。 Trie的一般缺点是需要大量内存，这不是一个主要问题，因为这里的字母表大小只有11个。“0”到“9”之间的数字需要十个字符，点（“.”）需要一个字符。 其思想是将IP地址存储在Trie节点中，并在最后一个节点中存储相应的域名。下面是C++中的C风格实现。
CPP
// C based program to implement reverse DNS lookup #include<stdio.h> #include<stdlib.h> #include<string.h> // There are atmost 11 different chars in a valid IP address #define CHARS 11 // Maximum length of a valid IP address #define MAX 50 // A utility function to find index of child for a given character 'c' int getIndex( char c) { return (c == '.' )? 10: (c - '0' ); } // A utility function to find character for a given child index. char getCharFromIndex( int i) { return (i== 10)? '.' : ( '0' + i); } // Trie Node. struct trieNode { bool isLeaf; char *URL; struct trieNode *child[CHARS]; }; // Function to create a new trie node. struct trieNode *newTrieNode( void ) { struct trieNode *newNode = new trieNode; newNode->isLeaf = false ; newNode->URL = NULL; for ( int i=0; i<CHARS; i++) newNode->child[i] = NULL; return newNode; } // This method inserts an ip address and the corresponding // domain name in the trie. The last node in Trie contains the URL. void insert( struct trieNode *root, char *ipAdd, char *URL) { // Length of the ip address int len = strlen (ipAdd); struct trieNode *pCrawl = root; // Traversing over the length of the ip address. for ( int level=0; level<len; level++) { // Get index of child node from current character // in ipAdd[]. Index must be from 0 to 10 where // 0 to 9 is used for digits and 10 for dot int index = getIndex(ipAdd[level]); // Create a new child if not exist already if (!pCrawl->child[index]) pCrawl->child[index] = newTrieNode(); // Move to the child pCrawl = pCrawl->child[index]; } //Below needs to be carried out for the last node. //Save the corresponding URL of the ip address in the //last node of trie. pCrawl->isLeaf = true ; pCrawl->URL = new char [ strlen (URL) + 1]; strcpy (pCrawl->URL, URL); } // This function returns URL if given IP address is present in DNS cache. // Else returns NULL char *searchDNSCache( struct trieNode *root, char *ipAdd) { // Root node of trie. struct trieNode *pCrawl = root; int len = strlen (ipAdd); // Traversal over the length of ip address. for ( int level=0; level<len; level++) { int index = getIndex(ipAdd[level]); if (!pCrawl->child[index]) return NULL; pCrawl = pCrawl->child[index]; } // If we find the last node for a given ip address, print the URL. if (pCrawl!=NULL && pCrawl->isLeaf) return pCrawl->URL; return NULL; } //Driver function. int main() { /* Change third ipAddress for validation */ char ipAdd[][MAX] = { "107.108.11.123" , "107.109.123.255" , "74.125.200.106" }; char URL[][50] = { "www.samsung.com" , "www.samsung.net" , "www.google.in" }; int n = sizeof (ipAdd)/ sizeof (ipAdd[0]); struct trieNode *root = newTrieNode(); // Inserts all the ip address and their corresponding // domain name after ip address validation. for ( int i=0; i<n; i++) insert(root,ipAdd[i],URL[i]); // If reverse DNS look up succeeds print the domain // name along with DNS resolved. char ip[] = "107.108.11.123" ; char *res_url = searchDNSCache(root, ip); if (res_url != NULL) printf ( "Reverse DNS look up resolved in cache:%s --> %s" , ip, res_url); else printf ( "Reverse DNS look up not resolved in cache " ); return 0; } |
输出：
Reverse DNS look up resolved in cache:107.108.11.123 --> www.samsung.com
输出：
Reverse DNS look up resolved in cache:107.108.11.123 --> www.samsung.com
请注意，上述Trie实现假定给定的IP地址不包含除{0’，1’，9’，’.}以外的字符。如果用户提供了一个包含其他字符的无效IP地址，该怎么办？这个问题可以通过以下方法解决： 正在验证输入的IP地址 在将其插入Trie之前。我们可以使用讨论过的方法 在这里 用于IP地址验证。 Java实现如下所示：
JAVA
import java.util.HashMap; import java.util.Map; public class ReverseDNSLookup { public void insert(TrieNode node, String[] ipAdd, String[] urls) { for ( int i= 0 ;i<ipAdd.length;i++) this .insertUtil(node, ipAdd[i], urls[i], 0 ); } public void insertUtil(TrieNode node, String ipAddr, String url, int pos) { TrieNode temp = null ; if (node.child.containsKey(ipAddr.charAt(pos))) { temp = node.child.get(ipAddr.charAt(pos)); } else { temp = new TrieNode(); node.child.put(ipAddr.charAt(pos), temp); } if (pos==ipAddr.length()- 1 ) { temp.url = url; return ; } this .insertUtil(temp, ipAddr, url, pos+ 1 ); } public String search(TrieNode node, String ipAddr, int pos) { TrieNode temp = null ; if (pos==ipAddr.length()- 1 ) { temp = node.child.get(ipAddr.charAt(pos)); if (temp!= null ) return temp.url; } if (node.child.containsKey(ipAddr.charAt(pos))) { temp = node.child.get(ipAddr.charAt(pos)); return this .search(temp, ipAddr, pos+ 1 ); } return "No url associated/Invalid IP address" ; } public static void main(String []args) { ReverseDNSLookup r = new ReverseDNSLookup(); String[] ipAdd = { "107.108.11.123" , "107.109.123.255" , "74.125.200.106" }; String[] urls = { "www.samsung.com" , "www.samsung.net" , "www.google.in" }; TrieNode root = new TrieNode(); r.insert(root, ipAdd, urls); //System.out.println(root); System.out.println( "74.125.200.106 : " + r.search(root, "74.125.200.106" , 0 )); System.out.println( "107.109.123.245 : " + r.search(root, "107.109.123.245" , 0 )); } } class TrieNode { Map<Character, TrieNode> child; String url; TrieNode() { this .child = new HashMap<>(); } public String toString() { return child.toString()+ " : " +url; } } // This code is contributed by Akhilesh Singla |
Javascript
<script> class TrieNode { constructor() { this .child = new Map(); } toString() { return this .child.toString()+ " : " +url; } } function insert(node,ipAdd,urls) { for (let i = 0; i < ipAdd.length; i++) this .insertUtil(node, ipAdd[i], urls[i], 0); } function insertUtil(node, ipAddr,url,pos) { let temp = null ; if (node.child.has(ipAddr[pos])) { temp = node.child.get(ipAddr[pos]); } else { temp = new TrieNode(); node.child.set(ipAddr[pos], temp); } if (pos==ipAddr.length-1) { temp.url = url; return ; } this .insertUtil(temp, ipAddr, url, pos+1); } function search(node,ipAddr, pos) { let temp = null ; if (pos==ipAddr.length-1) { temp = node.child.get(ipAddr[pos]); if (temp!= null ) return temp.url; } if (node.child.has(ipAddr[pos])) { temp = node.child.get(ipAddr[pos]); return this .search(temp, ipAddr, pos+1); } return "No url associated/Invalid IP address" ; } let ipAdd = [ "107.108.11.123" , "107.109.123.255" , "74.125.200.106" ]; let urls = [ "www.samsung.com" , "www.samsung.net" , "www.google.in" ]; let root = new TrieNode(); insert(root, ipAdd, urls); //System.out.println(root); document.write( "74.125.200.106 : " + search(root, "74.125.200.106" , 0)+ "<br>" ); document.write( "107.109.123.245 : " + search(root, "107.109.123.245" , 0)+ "<br>" ); // This code is contributed by patel2127 </script> |
输出：
74.125.200.106 : www.google.in107.109.123.245 : No url associated/Invalid IP address
Python3的实现：
Python3
# Trie Node class TrieNode: def __init__( self ): self .child = [ None ] * 11 self .url = None self .is_end = False class Trie: def __init__( self ): self .root = TrieNode() def getIndex( self , c): # For the . (dot) in IP address, we'll use the 10th index in child list return 10 if c = = '.' else int (c) def insert( self , ip, domain): cur = self .root n = len (ip) for level in range (n): # We'll use the digits of IP address to form the trie structure idx = self .getIndex(ip[level]) if cur.child[idx] is None : # Create a new trie node if not available for a particular digit # and assign to the respective index cur.child[idx] = TrieNode() cur = cur.child[idx] # At the end, we'll map the domain name and mark the end node cur.url = domain cur.is_end = True def search_domain( self , ip): cur = self .root n = len (ip) # Traverse through the trie structure with all digits in ip address for level in range (n): idx = self .getIndex(ip[level]) if cur.child[idx] is None : return "Domain name not found" cur = cur.child[idx] # Returns the url when all the digits in ip found if cur and cur.url: return cur.url return "Domain name not found" # Driver Code ip = [ "107.108.11.123" , "107.109.123.255" , "74.125.200.106" ] domain = [ "www.samsung.com" , "www.samsung.net" , "www.google.co.in" ] trie = Trie() for idx in range ( len (ip)): trie.insert(ip[idx], domain[idx]) print (trie.search_domain( "107.109.123.255" )) print (trie.search_domain( "107.109.123.245" )) # This code is contributed by Abhilash Pujari |
输出：
www.samsung.netDomain name not found
本文由 库马尔·戈塔姆 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
